11726 2xn 타일링

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

dp 문제이다. 1x2 와 2x1 직사각형을 2xn에 타일링하는 경우를 세면 된다.

 

처음에 굉장히 막막했다. 이런 dp문제들을 사람들은 어떻게 푸는 건지 싶고.. 답지를 볼까 말까 고민을 많이 했지만 막상 답을 알고 풀고 나니까 dp 중에서는 나름 할만한 문제였다는 생각이 든다.

 

가장 처음 떠올린 생각은

 

1) 1/n-1, 2/n-2, 3/n-3 ... n-1/1 로 타일을 쪼개서 더한다.

이 생각이었다. 이렇게 코드를 짜게 되면

for(int i=1;i<n;i++){

    dp[i]+=dp[i]+dp[n-i];

}

뭐 이런 식으로 코드가 나오게 되는데 dp니까,, 하면서 시도해보았다. 그런데 아주 잠깐만 생각해봐도 1/n-1과 n-1/1에서 1x2 타일만 쓰는 경우가 중복된다는 것을 알 수 있다.(dp[n-1]에서 1x2타일만 쓰는 한 가지의 경우만을 가지고 온 것이다) 따라서 이러한 식으로 접근하면 안된다. +) 두개로만 자르는게 아니라 3등분, 7등분을 할 수도 있고 이것이 저 위의 경우에 포함된다는 걸 완벽하게 알기는 어렵다고 생각했다.

 

2) 1등분, 2등분, 3등분.... n등분

이렇게 된다고 생각하니까 코드도 복잡해지고 1등분은 그럼 dp를 쓰는 이유를 잃어버리는 것이 아닌가.. 그렇지만 쪼개지 않고 나올 수 있는 경우가 있을 수도 있지 않을까...(물론 이 생각은 틀린 생각이었다). 또한 1번과 마찬가지로 겹치는 경우를 보장해줄 수 없다는 문제가 있다고 생각했다. 

 

3) 1x2타일을 먼저 세웠을 경우와, 2x1타일을 먼저 세웠을 경우로 쪼개어 생각하기 (답!!!)

사실 dp[i]가 dp[i-1]과 관련이 있을지 dp[i/2], dp[i/3]과 관련이 있을지를 결정해야(알아내야) 문제를 풀 수 있는데 1,2가 모두 dp[i/2] ...(또는 그 외) 와 관련된 경우를 생각한 것들이라서 i-1(바로 이전 항)과 관련이 있을까 생각해 보았다. 1/2에서 보장할 수 없었던 것이 겹치는 경우라서 그것을 보장할 수 있는지를 가장 먼저 따졌다. 

 

 (1) 2x1타일(세로)이 맨 첫번째에 세워졌을 때

 2x1이 가장 먼저 세로로 세워지면 우리가 채워야 할 부분은 n-1개의 타일이다. 이 경우 타일을 세우는 경우의 수는 dp[n-1]로 간단하다. 

 내가 또 생각했던 경우는 맨 첫번째가 아니라 마지막에 2x1타일을 세우는 경우는 생각하지 않아도 되는 건가?? 였는데 마지막에 타일을 세 워도 첫 번째(시작하는) 타일 모양은 (1) (2)가 유일하므로(따라서 (1) (2)를 따지면 마지막에 세우는 경우도 고려됨) 마지막에 타일을 세우는  경우는 고려하지 않아도 된다는 결론을 내릴 수 있었다.

 

 (2) 1x2타일(가로) 두개가 정사각형을 이루면서 맨 첫번째와 두번째를 차지할 때

 2x1이 들어가는 경우를 고려하였으니 1x2 타일이 들어가는 경우도 고려해야 한다. 그러나 1x2타일이 들어가기 위해서는 첫번째 두 칸을 차지해야 하므로, 무조건 정사각형 모양을 띄면서 들어갈 수 밖에 없다. 이 경우 남은 칸은 n-2 이므로 타일을 세우는 경우의 수는 dp[n-2]이다. (1) (2)가 중복되는 경우는 앞머리 모양이 다르므로 있을 수가 없고, (1)에서 언급했듯이 맨 뒤에(또는 아무데나) 1x2타일을 넣는다고 해도 앞머리 모양은 (1) (2)가 유일하므로 (1) (2)에서 모두 카운트 될 것이다.

 

따라서 (1) (2)만 따져주면 되고, 이를 점화식으로 만들면

dp[i]=dp[i-1]dp[i-2]

초기조건은 i=1 무조건 2x1하나밖에 못들어가므로 1 : dp[1]=1,

i=2 2x1두개가 나란히 들어가거나 1x2두개가 나란히 들어가는경우 : dp[2]=2

 

따라서 피보나치 수열의 형태를 띄게 된다.

 

코드: 

#include <cstdio>

int dp[1001];

int main(){

int n;

scanf("%d",&n);

dp[0]=0;

dp[1]=1;

dp[2]=2;

for(int i=3;i<=n;i++){

dp[i]=(dp[i-1]+dp[i-2])%10007;

}

printf("%d\n",dp[n]);

}