99클럽 코테 스터디 22일차 TIL

문제

프로그래머스 - 산 모양 타일링

해결 방법

1. DP를 사용하여 위에 삼각형이 있는 경우와 없는 경우에 맞춰 계산해준다.

정답 코드 - JAVA

import java.util.*;

class Solution {
    public int solution(int n, int[] tops) {
        int[][] dp = new int[n + 1][2];
        
        dp[1][0] = 1;
        if (tops[0] == 1) { // 위에 삼각형이 있다면 
            dp[1][1] = 3;
        } else { // 위에 삼각형이 없다면
            dp[1][1] = 2;
        }
        
        for (int i = 2; i <= n; i++) {
            dp[i][0] = (dp[i - 1][0]+ dp[i - 1][1]) % 10007;
            if (tops[i - 1] == 1) { // 삼각형이 존재한다면
                dp[i][1] = (dp[i - 1][0] * 2 + dp[i - 1][1] * 3) % 10007;
            } else {
                dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 2) % 10007;
            }
        }
        return (dp[n][0] + dp[n][1]) % 10007;
    }
}

오늘의 회고

DP의 점화식은 항상 헷갈리고 어렵다.