- 문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
- 입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
2
8
12
- 출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
3
171
2731
- 정의
D[N] = 1×2, 2×1과 2×2 타일로 채우는 방법의 수
= D[1*2] + D[2*1] + D[2*2]
= 2*D[N-1] + D[N-2] (XXX)
= D[N-1] + 2*D[N-2] (OOO)
2*2를 하나짜리로 쳐서 1개의 타일이라고 생각했는데 크기 2가 빠지니까 n-2이다.
(2*1를 2개 놓는 꼴이니까 n-2과 같은 게 아닐까 추측..)
- 예외
n = 1 => 2*1
2*1 만 놓을 수 있으므로 총 1가지.
( ∵ 2*1에다가 1*2와 2*2를 넣기에는 세로가 짤려서 못 넣음)
10007을 안나눠줘도 값은 같은데 혹시 모를 큰 값에 대비해서 나눠주는 것일까..?
찾아본 결과 :
저장할 수 있는 수의 범위가 없다면 마지막이 아닌 중간에 %10007을 하는 것과 마지막에 %10007을 하는 것의 결과가 똑같음을 증명할 수 있습니다. 여기서는 수가 int 범위까지만 갈 수 있기 때문에 중간에 %10007을 안 하면 오히려 잘못된 값으로 오버플로우하게 됩니다.
직감적으로 와닿지 않는다면 10진수의 수에서 일의 자리만 구하는 경우를 생각해보시면 됩니다. 덧셈과 곱셈만으로 이루어진 연산들에서 10의 자리를 넘어가는 건 아무 의미가 없으니, 매 연산마다 그 1의 자리 하나만 추적하고 있어도 결과는 똑같이 나옵니다. 마찬가지로, 이 수를 10007진수라고 생각하고 끝자리 한 자리만 추적해도 결과는 같습니다.
- 풀이
public class Main {
static int[] memo;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
memo = new int[10001];
int n = Integer.parseInt(br.readLine());
System.out.println( TopDown(n) ); // 1. Top-Down 방식
System.out.println( BottomUp(n) ); // 2. Bottom-Up 방식
br.close();
}
private static int TopDown(int n) {
if( n<2 ){
return 1;
}
if( memo[n]>0 ){
return memo[n];
}
memo[n] = ( TopDown(n-1) + 2*TopDown(n-2) )%10007;
return memo[n];
}
private static int BottomUp(int n) {
memo[0] = memo[1] = 1;
for( int i=2;i<=n;i++ ){
memo[i] = ( memo[i-1] + 2*memo[i-2] )%10007;
}
return memo[n];
}
}
'알고리즘 > 다이나믹 프로그래밍' 카테고리의 다른 글
[DP] 백준 11052 - 카드 구매하기 (0) | 2022.04.02 |
---|