[프로그래머스] Lv3. 산 모양 타일링

문제 풀이 방법 

만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 
10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요.

 

 

문제에서 제공해준 아래의 예시를 통해 한단계씩 접근 해보겠습니다.

 

 

정삼각형 또는 마름모 타일로 빈 곳이 없도록 채워야 하는 모양은 다음과 같습니다.

이 모양을 두 부류로 나누면 아래와 같습니다.

삼각형 4개로 이루어진 큰 삼각형 모양과 삼각형 3개로 이루어진 사다리꼴 모양이 있습니다.

 

각 모양을 채울 수 있는 갯수는 몇개가 존재할까요?

 

먼저, 삼각형 4개로 이루어진 큰 삼각형 모양을 채우는 방법은 총 4가지 방법이 존재합니다.

 

다음으로 삼각형 3개로 이뤄어진 사다리꼴 모양을 채우는 방법은 총 3가지 방법이 존재합니다.

 

먼저, 위에 있는 삼각형을 제외한 아랫 부분을 기준으로 점화식을 세워 보겠습니다.

 

이렇게 3개의 삼각형으로 이루어진 것을  N = 0 이라고 가정합니다.

 

 

 

 

N = 0일땐, 아래 그림과 같이 3개로 채울 수 있습니다.

 

 

초록색 점선으로 묶은 모양을 왼쪽 마름모라고 칭하고, 빨간색 점선으로 묶은 모양을 오른쪽 마름모라고 칭하겠습니다.

 

삼각형으로만 이루어진 모양 1개 + 삼각형과 왼쪽 마름모인 경우 모양 1개 + 오른쪽 마름모와 삼각형인 경우 1개로 총 3개로 이루어져 있습니다.

 

 

N = 1일땐, 어떻게 될까요?

 

아래 그림과 같이 8개가 됩니다.

 

dp 점화식을 구하기 위해선, 조건이 같은 것끼리 묶어야 합니다.

이 문제에서의 조건은 끝모양이 마름모이거나 삼각형인것을 의미합니다.

 

왼쪽 마름모로 끝나는 경우는 몇개가 될까요?

 

끝이 왼쪽 마름모 모양인 경우엔 3개가 존재합니다.

 

N = 0 일때, 타일링할 수 있는 갯수와 같게 됩니다.

N = 0 일때는 3가지 경우가 존재했기 때문에,  n = 1에서 3개가 추가됩니다.

 

나머지는 어떻게 될까요?

삼각형으로만 이루어진 경우와 오른쪽 마름모와 삼각형으로 이루어진 경우는 n이 커질수록 2배의 갯수를 가지게 됩니다.

반면, 삼각형과 왼쪽 마름모로 이루어진 경우는 n이 커질수록 1개의 갯수가 추가되게 됩니다.

 

이 규칙을 적용해서 점화식을 세우면 어떻게 될까요?

 

먼저, 각 특징 별로 추가되는 경우를 그림으로 나타내면 다음과 같습니다.

 

짝지어준 경우를 A,B,C,D라고 가정합니다.

A,B인 경우에는 똑같이 2배로 늘어나기 때문에 같은 경우로 봐주고, 다시 하나로 묶어줍니다.

dp로 2차원 배열을 사용해서 점화식을 세워보겠습니다.

끝나는 모양이 마름모인 경우와 그렇지 않은 경우로 나눠 생각하면, 2가지로 나뉠 수 있습니다.

끝나는 모양이 마름모가 아닌 경우는 A,B를 묶고, 끝나는 모양이 마름모인 경우는 C 1개 입니다.

 

A,B의 그룹을 index 0에 할당하고, C의 그룹을 index 1에 할당하면, 아래와 같은 점화식이 나옵니다.

dp[n][0] = dp[n-1][0] * 2 + dp[n-1][1]; (A그룹 * 2) + (B그룹 1개)
dp[n][1] = dp[n-1][0] + dp[n-1][1];

 

왜 dp[n][1] = dp[n-1][0] + dp[n-1][1] 인가요?

 

끝나는 모양이 마름모인 경우는 이전 경우에 나올 수 있는 모든 경우를 의미합니다.

n = 0 일때, 나올 수 있는 경우는 3가지 였고, 이를 n = 1일때, 같은 맥락으로 점화식으로 표현하는 경우

dp[0][0] = 2, dp[0][1] = 1이 되어서, 총 3가지가 된 것이였습니다.

 

n = 1 일때, 끝부분이 마름모로 끝나는 경우는 이전 n = 0일때 나올 수 있는 모든 경우와 같게 됩니다. 그 이유는 단지 마름모 모양만 붙이기 때문입니다. 

따라서, n = 1일때 dp[1][1] = dp[0][0] + d[0][1]이 되고, 이를 점화식으로 세우는 경우 dp[n][1] = dp[n-1][0] + dp[n-1][1]이 됩니다.

 

점화식을 세웠으니, 끝난 줄 알았죠? 아직 윗변에 세워질 삼각형을 고려해 주어야 합니다.

 

이 모양의 점화식은 세웠으나

 

 

이 모양일때의 점화식을 다시 고려해야 합니다.

 

윗변에 삼각형이 추가된다고해서 달라지는 점이 있나요?

 

달라지는 점이 있습니다. A 경우를 예시로 어떤 점이 달라지는지 알아보겠습니다.

 

 

윗변에 삼각형이 있게됨으로 인해 기존 2배로 늘어나던 경우가 3배로 늘어나게 되었습니다.

 

나머지 경우도 전부 확인해보겠습니다.

 

윗변에 삼각형이 생기면서, A의 경우는 3배, B의 경우는 2배, C의 경우는 그대로 유지됩니다.

즉, 윗변에 삼각형이 없는 경우와 삼각형이 있는 경우의 점화식이 달라지게 됩니다.

 

윗변에 삼각형이 있는 점화식은 어떻게 될까요?

 

dp로 2차원 배열을 사용해서 점화식을 세워보겠습니다.

마찬가지로 A,B의 그룹을 index 0에 할당하고, C의 그룹을 index 1에 할당하면, 아래와 같은 점화식이 나옵니다.

dp[n][0] = dp[n-1][0] * 3 + dp[n-1][1] * 2;
dp[n][1] = dp[n-1][0] + dp[n-1][1];

 

이제, 점화식을 기반으로 코드로 구현 해보겠습니다.

 

구현 코드

import java.util.*;

class Solution {
    
    private int[][] dp;
    private final int MOD = 10007;
    
    public int solution(int n, int[] tops) {
        int answer = 0;
        
        dp = new int[n + 1][3];
        
        if(tops[0] == 1) {
            dp[0][0] = 3;
        }else {
            dp[0][0] = 2;
        }
        
        dp[0][1] = 1;
        
        for(int i = 1; i < n; i++) {
            
            if(tops[i] == 1) {
                dp[i][0] = dp[i-1][0] * 3 + dp[i-1][1] * 2;
            }else {
                dp[i][0] = dp[i-1][0] * 2 + dp[i-1][1];
            }
            
            dp[i][1] = dp[i-1][0] + dp[i-1][1];
            
            dp[i][0] %= MOD;
            dp[i][1] %= MOD;
        }
        
        answer = (dp[n-1][0] + dp[n-1][1]) % MOD;      
        return answer;
    }
}

 

이 문제에서 주의할 점은 시작할때 윗변에 삼각형이 놓여있는 모양으로 시작할 수 있다는 점입니다.

이런 경우 dp[0][0] 즉, 마름모로 끝나지 않는 모양은 총 3개가 됩니다.

 

그림으로 설명하면 다음과 같습니다.

dp[0][0]이 2개에서 3개로 늘어나고, dp[0][1]은 그대로 진행됩니다.

 

 

윗변에 삼각형이 존재하는 경우와 존재하지 않는 경우를 조건문을 통해서 다른 점화식을 적용시킵니다.

즉, dp[i][0]일때만 달라지게 됩니다.

 if(tops[i] == 1) {
                dp[i][0] = dp[i-1][0] * 3 + dp[i-1][1] * 2;
            }else {
                dp[i][0] = dp[i-1][0] * 2 + dp[i-1][1];
            }
            
            dp[i][1] = dp[i-1][0] + dp[i-1][1];

 

dp[i][1]인 경우엔 윗변에 삼각형의 유무에따라 점화식이 변하지 않기 때문에, 같은 로직을 두 경우에 모두 적용시킵니다.

 

시간 복잡도

O(N)

완전 탐색

 

출력 결과