BOJ 11726 2 x n 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

//(dp[i]//)를 다음과 같이 정의하자.

 

//(dp[i]//): 2 x i 크기의 직사각형을 1 x 2, 2 x 1 타일로 채우는 방법의 수

 

 

#include <cstdio>

int main() {
    int n;
    scanf("%d",&n);
    int dp[n+1];
    dp[0] = 1, dp[1] = 1;
    for(int i=2;i<=n;++i)
        dp[i] = (dp[i-1] + dp[i-2])%10007;

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

 

점화식이 이렇게 간단하지만, 점화식을 찾는데 한참 걸렸다. 1차원에서 답을 못 찾아 2차원으로 갔지만 예상했던 답과 다른 출력을 내보내 디버깅하느라 한참 시간을 썼는데, 알고 보니 점화식에 문제가 있었다.

이전에 풀었던 

 

https://yunjae-gong.tistory.com/11

BOJ 2293 동전 1

문제에서도 비슷한 어려움이 있었지만, 이번에는 그 정도가 심했다.

 

알고리즘 수업, 겨울방학 스터디 이후로 DP 문제는 한동안 접하지 않아서도 있겠지만, 

DP문제 접근에 있어 크게 두 가지 문제가 있는것 같다.

  1. 직관 부족

  2. 왜 이게 되는지에 대한 궁금증

 

동전 문제도 문제 난이도에 비해 꽤 시간이 걸렸지만, 이 문제는 장장 2시간 가까이 경우를 제대로 나누지 못하고 같은 곳에서 빙빙 돌았다. 

 

dp[5] = dp[4] + | 일 것 같다는 생각은 했지만, 그다음 dp[5] = dp[4] + = 경우를 생각하지 못했다. 

 

 

DP문제들은 알고리즘 수업 필기/자료 복습과 병행해 풀어 나가는 것이 좋을것같다.