두 개의 숫자 n과 m이 주어지며, 각각 방 바닥의 길이와 너비를 나타냅니다. 이때 목표는 1×m 크기의 타일을 사용하여 n×m 크기의 바닥을 채울 수 있는 서로 다른 배치 방법의 수를 구하는 것입니다.
예시
입력
n = 3, m = 2
출력
1 x m 크기 타일로 n x m 크기 바닥을 채우는 방법의 수: 3
설명
세 개의 1×2 타일을 아래 그림과 같이 배치할 수 있는 방법이 총 세 가지입니다.
입력
n = 3, m = 3
출력
1 x m 크기 타일로 n x m 크기 바닥을 채우는 방법의 수: 2
설명
세 개의 1×3 타일을 모두 세로로 배치하거나, 모두 가로로 배치하는 단 두 가지 방법만 존재합니다.
접근 방식
이 문제는 동적 프로그래밍(Dynamic Programming)으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- n이 m보다 작으면서 값이 1인 경우, 1×m 크기의 타일 하나만 놓일 수 있으므로 방법의 수는 1입니다.
- n이 m과 같으면, n개의 1×m 타일을 모두 세로로 놓는 방법과 모두 가로로 놓는 방법, 즉 두 가지 방법이 있습니다.
- n이 m보다 크면, 이전까지 계산한 값들을 활용하여
ways[n-1] + ways[m-1]로 방법의 수를 구합니다.
알고리즘 단계
- 바닥과 타일의 크기를 나타내는 정수 n과 m을 입력받습니다.
- 함수
ways_tile_floor(int N, int M)는 크기를 전달받아 n×m 크기 바닥을 1×m 타일로 채우는 방법의 수를 반환합니다. - 길이가 N+1인 배열
arr[]을 선언하여, 각 인덱스 i(현재 바닥의 길이)에 해당하는 배치 방법의 수를 저장합니다. arr[0]은 타일을 놓을 공간이 없으므로 0으로 초기화합니다.- for 루프를 이용해 i=1부터 i=N까지 배열을 순회합니다. 각 i에 대해 i>M이면 이전 값들을 이용해
arr[i] = arr[i-1] + arr[i-M]으로 계산합니다. - i=1이거나 i<M인 경우에는
arr[i] = 1로 설정합니다. - i=M인 경우에는
arr[i] = 2로 설정합니다. - 루프가 종료되면
arr[N]에 전체 배치 방법의 수가 저장됩니다. arr[N]을 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int ways_tile_floor(int N, int M){
int arr[N + 1];
arr[0] = 0;
for (int i = 1; i <= N; i++){
if (i > M){
arr[i] = arr[i - 1] + arr[i - M];
}
else if (i < M || i == 1){
arr[i] = 1;
} else {
arr[i] = 2;
}
}
return arr[N];
}
int main(){
int n = 3, m = 2;
cout<<"Count the number of ways to tile the floor of size n x m using 1 x m size tiles are: "<<ways_tile_floor(n, m);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count the number of ways to tile the floor of size n x m using 1 x m size tiles are: 3