2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력 :
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력 :
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
접근 방법
저는 처음 2차원 배열을 0으로 초기화 후에 직사각형이 채워지면 1 또는 +1로 갱신하는 것으로 생각했습니다.
따라서 2중 for문으로 돌려서 직사각형을 채우려고 했습니다.
만약 2*3인 직사각형이라면 ㅁㅁㅁ ㅁㅁㅁ이겠죠?
이 때 직사각형은 2*1과 1*2 타일로 채워야 하니까
1번 방법은 | | | | | | 로 1*2타일 3개로 채우고 2번 방법은 --| --| 로 1*2타일 1개 + 2*1타일 2개로 채웁니다. 3번 방법은 |-- |-- 로 2번 방법과 순서를 바꿔 직사각형을 채웁니다.
총 3가지 방법이 나오는데, 10,007로 나눈 나머지를 출력하면 총 방법의 수는 3이 나옵니다.
이후에는 동빈나님의 동영상과 게시글을 참고해보았습니다.
가장 마지막에 오는 타일을 기준으로 생각했을 때, 가능한 경우는 두 가지 입니다. 위의 예제에서도 보셨듯이 전체가 N의 길이라면 총 길이 N일 때, N - 1총 길이 N일 때, N - 2 N-1개 일 때는 1*2블럭 하나가 N-2개일 때는 2*1블럭 두개가 필요합니다. 따라서 각각의 경우일 때 필요한 방법은 한 가지 입니다.
점화식은 dp[i] = dp[i - 1] + dp[i - 2]로 세울 수 있습니다.
정답 코드
#include <iostream>
using namespace std;
int dp[1001];
int main() {
int n;
cin >> n;
dp[1] = 1; // n이 1일 때는 한 가지 경우만 존재
dp[2] = 2; // n이 2일 때는 두 가지 경우만 존재합니다.
for(int i = 3; i <= n; i++){
dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
// 반복하다보면 자료형의 크기를 넘을 수 있기 때문에
// 연산할 때마다 10007로 나눈 나머지를 저장해야 합니다.
}
cout << dp[n];
return 0;
}
댓글