[2024 KAKAO WINTER INTERNSHIP] 산 모양 타일링

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

프로그래머스

 

dp로 풀 수 있는 문제이다. 처음에 문제에서 말하는 n을 다른 의미로 해석해서 점점 이상한 길을 가게 되었는데.. 문제에서 의미하는 대로 n을 생각해야 한다.

 

n = 3일 때 만들어지는 도형을 채울 수 있는 경우의 수를 dp[3]이라고 하자. 이때 dp[3]의 앞 순서인 dp[2]는 다음과 같이 두 가지 경우로 나뉠 수 있다.

• 마름모로 채워져 끝나는 경우 (즉, 파란색 부분을 dp[2]에서 마름모 형태로 채우는 경우)
• 마름모가 아니게 채워져 끝나는 경우 (즉, 파란색 부분을 dp[3]에서 채우는 경우)

 

따라서 마름모 형태로 채워져 끝나는 경우와 그렇지 않은 경우를 나눠서 생각해야 되고, 이를 각각 dp[n][0], dp[n][1]이라고 하자.

• dp[n][0]: 마름모 형태로 채워져 끝나는 경우
• dp[n][1]: 마름모가 아니게 채워져 끝나는 경우

 

그리고 위에 정삼각형이 붙는 경우와 붙지 않는 경우까지 고려하면, 다음과 같은 규칙을 찾을 수 있다.

 

위 점화식대로 구현하면 된다.

import java.util.*;

class Solution {
    
    static final int mod = 10007;
    
    public int solution(int n, int[] tops) {
        int[][] dp = new int[n + 1][2];
        dp[1][0] = 1;
        dp[1][1] = tops[0] == 1 ? 3 : 2;
        
        for (int i = 2; i <= n; i++) {
            int n1 = tops[i - 1] == 1 ? 2 : 1;
            int n2 = tops[i - 1] == 1 ? 3 : 2;
            
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
            dp[i][1] = (dp[i - 1][0] * n1 + dp[i - 1][1] * n2) % mod;
        }
        
        return (dp[n][0] + dp[n][1]) % mod;
    }
}