Beakjoon 11726 2xn 타일링

17 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/11726

나의 풀이

n = 1부터 타일을 채울 수 있는 방법을 그려보면 다음과 같은 패턴을 찾을 수 있다. 위 그림에서 파랑색과 빨간색으로 칠해진 타일은 타일을 추가할 수 있는 최소 단위의 타일을 각각 나타낸 것이고 초록색 타일은 n-1번 타일, 보라색은 n-2번 타일이다.
위 그림에서 볼 수 있듯이 n-1번 타일에 파란색 타일을 추가하는 경우와 n-2번 타일에 빨간색 타일을 추가하는 경우 두 가지 경우를 합하면 n번 타일에서 만들 수 있는 경우의 수를 모두 구할 수 있다.
이를 점화식으로 표현하면 다음과 같다.
DP[i] = DP[i-1] + DP[i-2]

풀이 코드 : 11726 2xn 타일링

#include <iostream>
#include <vector>

using namespace std;

int DP[1000];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;

    DP[0] = 1;
    DP[1] = 2;
    for(int i=2;i<n;i++){
        DP[i] = (DP[i-2] + DP[i-1])%10007;
    }
    cout<<DP[n-1];
}

채점결과