[프로그래머스] LV3. 산 모양 타일링 문제 풀이

문제

 

풀이

고려해야할 점

• 타일은 위와 아래로 존재하고 있다. 이 문제는 위와 아래 타일에 각각의 경우에 따른 계산이 필요하다.
•   n의 최대 개수는 100,000 이므로 모든 경우의 수를 완전 탐색할 경우 시간 초과 문제가 발생한다. 

 

풀이 아이디어

• 다이나믹 프로그래밍
• 타일의 개수에 따른 점화식을 세워 계산한다. 이때 점화식은 위 타일 아래 타일 분리하여 계산하여야 한다. 

 점화식 계산 

• DP 배열은 2차원으로 생성. int[][] dp = new int[n+1][2]; 형식으로 선언하였다. 이때 배열의 첫 번째 인덱스는 몇 번째 타일인지를 나타내고 두 번째 인덱스는 위 타일인지 아래타일인지를 나타낸다. 이 코드에서는 위의 인덱스를 0으로 아래를 1로 표시한다. 

아래 타일 점화식

아래 타일(dp[n][1])은 두 가지 경우를 포함합니다.

1. n번째 아래 타일이 단독으로 존재하는 경우: 이 경우의 수는 dp[n][0]만큼 존재합니다.
2. n번째 아래 타일이 위에 있는 타일과 결합하여 마름모 모양을 이루는 경우: 이 경우의 수는 dp[n-1][1]만큼 존재합니다.

따라서 아래 타일에 대한 점화식은 다음과 같이 표현할 수 있습니다:

dp[n][1]  = dp[n−1][1] + dp[n][0]

위 타일 점화식

위 타일(dp[n][0])은 위에 추가적으로 타일을 붙이는 경우와 그렇지 않은 경우를 고려하여 계산합니다.

1. 위에 타일이 추가로 붙지 않은 경우: 이 경우의 수는 dp[n-1][1] + dp[n-1][0]로 계산됩니다.
2. 위에 타일이 추가로 붙어 마름모를 형성하는 경우: 이 경우의 수는 dp[n-1][1] * 2 + dp[n-1][0]로 계산됩니다.

이를 종합하면 위 타일에 대한 점화식은 다음과 같습니다:

dp[n][0] = dp[n−1][1]×2 + dp[n−1][0]  위에 타일이 있는 경우

dp[n][0] = dp[n−1][1] + dp[n−1][0] 위에 타일이 없는 경우

 

코드

class Solution {
    public int solution(int n, int[] tops) {
        int[][] dp = new int[n+1][2];
      
        // dp 초기화 
        dp[0][1] = 1;
        dp[0][0] = 1;
        
        // dp 계산 
        for(int i = 1; i<= n; i++){
            dp[i][0] = (dp[i-1][0] + dp[i-1][1]*(1+tops[i-1]))%10007;  
            dp[i][1] = (dp[i][0] + dp[i-1][1])%10007; 
        }
        
        return dp[n][1];
    }
}