[BOJ] 백준 11726 2xn 타일링 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

앞에 풀었던 2193번 이친수, 1904번 01타일 과 상당히 비슷한 문제이다.

 

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 출력하면 된다.

 

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

 

 

💭 풀이 과정

 

 

| 를 2x1 사각형, == 를 1x2 사각형으로 가정하겠다.

 

N = 1 인 경우 1가지    |

 

N = 2 인 경우 2가지    | | , ==

 

N = 3 인 경우 3가지    | | | , == | , | ==

 

N = 4 인 경우 5가지    | | | | , == | | , | | == , | == | , == ==

 

 

 

 

이런 방식으로 변화한다.

여기서 두 가지의 규칙을 찾을 수 있었다.

 

 

1) N-2 번째 경우의 수와 N-1 번째 경우의 수를 합한 것이 N 번째 경우의 수가 된다.

 

N-2 번째 경우들의 우측에 == 를 더한 것과 N-1 번째 경우들의 우측에 | 를 추가한 것이 N 번째 경우들이 되었다.

 

2) 결국 경우의 수가 피보나치 수열로 변한다는 말이다.

 

 

두 아이디어 모두 소스코드는 동일하다.

 

 

 

작성 언어: C++

 

#include <cstdio>

int dp[1010] = {0, };

void solve(int num){
    dp[1] = 1;  dp[2] = 2;
    for (int i = 3; i <= num; ++i) {
        dp[i] = ( dp[i-2] + dp[i-1] ) % 10007;
    }
}

int main(){
    int nLength;
    scanf("%d", &nLength);
    solve(nLength);
    printf("%d\n", dp[nLength]);
    return 0;
}

 

 

 

 

🏆 배운 점

 

 

바로 앞에 풀어본 두 문제와 유형이 유사해서 무난하게 풀었던 문제이다.

 

계속해서 dp 문제를 접하다보니, 어떤 전략으로 풀이에 접근을 할지 좀 도움이 되는 것 같다.