[Java DP] 프로그래머스 2 X n 타일링

Dynamic Programming의 대표적인 문제인 2XN 타일링 문제입니다.

 

문제

 

 

DP문제는 케이스를 나누는 것이 중요합니다.

케이스를 나눌 때는 문제를 다 풀기 직전의 상황부터 거꾸로 푸는 방법이 좋습니다.

 

바닥의 세로 길이는 2로 고정되어있고, 가로의 길이는 60,000이하의 자연수 입니다.

그러므로 문제를 풀 때는 변수로 주어지는 가로의 길이를 기준으로 진행하여야 합니다.

 

가로의 길이가 n일경우 n-1까지 타일이 꽉 차있다면 다음과 같은 경우가 있습니다.

 

Case1. n-1 개의 타일까지 꽉 차있는 경우

 

채울 수 있는 가로의 길이가 1밖에 없으므로, 이 경우는 단 1개의 타일만 채울 수 있습니다.

 

가로의 길이가 n-2까지 꽉 차있다면 다음 케이스가 가능합니다.

 

Case2. n-2개의 타일까지 꽉 차있는 경우

 

n-2개의 타일까지 꽉 차있다면 가로의 길이가 2가 남기 때문에 2가지의 경우가 생깁니다.

세로로 타일을 채우는것과 타일을 눕혀서 가로로 채우는 것이죠. 여기서 중요한 것이 있습니다.

 

세로로 타일을 세우는 경우는 Case 1에 포함됩니다.

 

 

그러므로 이런 경우는 새로운 케이스가 아닌, 원래 있는 케이스로 포함됩니다.

 

 

n-3개의 타일이 꽉 차있는 경우는 어떨까요?

 

 

 

위 케이스 모두 case1, case2에 포함됩니다. 케이스가 나뉘어 진 것을 확인했다면 나누어진 케이스일 때 분기인 case1과 case2만 나누어서 구현하면 됩니다.

 

최종적으로 나온 케이스는 다음과 같이 되겠네요

 

 

 

자 이제 문제를 풀 수 있는 점화식이 나옵니다.

 

 

F(n-3) = (F(n-1) + F(n-2)) * F(1) F(1) = 1 F(n-3) = F(n-2) + F(n-1)

위 식이 익숙하다면 아주 정상적인 현상입니다.

피보나치 수열과 같은 식이니까요!

 

위 식을 토대로 만든 코드는 아래와 같습니다.

public int solution(int n) {
	int a = 1;
    int b = 1;
    for (int i = 0; i < n - 1; i++) {
    // 숫자가 너무 커지는 것을 방지하기 위해 나머지를 구한다.
    	int c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return b;
}