[프로그래머스] 2 x n 타일링 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

 

 

풀이 방법

가로 N인 길이를 채우기 위해

N-1, N-2, N-3, ... 길이를 채운 상태에서 타일을 채운다고 생각해 보자.

 

1. N-1 길이

N-1 길이를 채운 상태에서 세로 타일을 하나 설치하면 N 길이의 타일을 채울 수 있다.

 

2. N-2 길이

N-2 길이 타일을 채운 상태에서 위의 두 방법으로 타일을 채워 N길이를 채울 수 있지만.

세로 타일을 두 개 설치하는것은 이미 N-1 길이 타일에서 끝에 세로 타일이 두개 연속으로 채워진 것과 동일한 상태이다.

오른쪽의 경우만 생각하면 된다.

 

3. N-3 길이

N-3인 경우에 끝에 타일을 채우는 모든 경우가 N-1, N-2일 때 채우는 방법과 모두 중복된다.

 

=> N 길이의 타일을 채우기 위해 N-1, N-2 길이의 타일을 채우는 방법을 더하면 된다.

 

 

간단하게 생각하여 아래의 두 타일을 붙여 총길이 N을 완성할 것인데 N-1에서 세로 타일하나, N-2에서 가로로 타일 2개를

붙여 N길이를 완성할 수 있으니 bottom-up 방식으로 N은 N-1, N-2의 합으로 알 수 있다.

 

전체 코드

using namespace std;

int solution(int n) {
    int answer = 0;
    
    int dp[60001];
    dp[1] = 1;
    dp[2] = 2;
    
    for(int i=3; i<=n; i++) {
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
    }
    
    answer = dp[n];
    return answer;
}