[C++] 백준 11726 - 2xn 타일링 (DP)

백준 11726번 2xn 타일링 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 

문제 링크

11726번: 2 ×n 타일링 (acmicpc.net)

11726번: 2×n 타일링

알고리즘

실버 3 문제인데 생각보다 안 떠올라서 어렵게 느껴졌다.

결국 노가다하다가 규칙은 찾아내었는데 마지막에 값이 너무 커지는 걸 생각을 못해, 마지막 출력에만 10007로 나누어주었다가 틀렸다.

1. dp 배열을 선언해 첫 번째와 두 번째 값을 초기화시킨다.
2. 직사각형을 붙이는 규칙은 두 가지이다. 첫 번째는 가로로 한 칸 차지하는 ㅣ 가 붙는 경우 --> dp [i-1] 만큼 더하기
3. 두 번째는 가로로 두 칸 차지하는 ㅡ 가 붙는 경우 --> dp [i-2]에서 두칸을 이어붙이면 되므로 dp [i-2] 만큼 더하기
4. 결국  dp [i]=dp [i-1]+dp [i-2]라는 피보나치수열과 같은 점화식이 나온다.
5. 마지막에 주의할 점이 10007로 나눈 값을 출력하라고 하는데 피보나치수열이기 때문에 n이 1000만큼 커져버리면 이미 int 값의 범위를 훨씬 초과해버려서 쓰레기 값이 나오기 때문에 연산할 때마다 차라리 1007로 나눠주는 방법이 있다.

 

코드

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    int dp[1001];
    dp[1]=1;
    dp[2]=2;
    cin>>n;

    for(int i=3;i<=n;i++){
        dp[i]=(dp[i-1]+dp[i-2])%10007;
    }
    cout<<dp[n]<<'\n';
    return 0;
}

 

제출 결과

항상 int범위를 생각하자....