[프로그래머스] (2024 KAKAO WINTER INTERNSHIP) 산 모양 타일링 / 자바(Java)

문제

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

프로그래머스

 

---

해설

경우의 수를 10007(큰 소수)로 나누어 return해야하는 점에서 단순 구현으로 해결할 수 없고

이전 값에서 다음 값을 아는 DP를 사용해 해결하는 문제입니다.

 

점화식 형태로 풀어내기 위해서 어떤 형태들을 만들 수 있는지 파악하고 다음 값에 영향을 주는 요소를 알아야 합니다.

기본 모형인 큰 정삼각형을 덮는 방식은 4가지 입니다.

 

1. 정삼각형 타일

2. 왼쪽 정삼각형 + 중간 정삼각형을 마름모 타일

3. 위쪽 정삼각형 + 중간 정삼각형을 마름모 타일

4. 오른쪽 정삼각형 + 중간 정삼각형을 마름모 타일

 

이때 특이사항으로는

3번의 경우는 tops[i]가 1일 때만 가능한 경우이며

4번의 경우는 다른 가능성과 달리 다음 삼각형을 만들때 영향을 주어 2번을 만들지 못합니다.

 

따라서 DP배열을 2차원배열로 만들어 dp[i][0] 은 4번을 경우인, dp[i][1]은 4번을 제외한 경우로 배열을 만들어 넣었습니다.

또한 각 DP를 계산할 때 tops[i]에 영향을 받아 if문을 통해 가능성을 계산해 줍니다.

 

tops[i]==0인 경우

1번

2번

4번

 

tops[i]==1인 경우

 

---

코드

class Solution {
    public int solution(int n, int[] tops) {
        int answer = 0;
        // dp[i][0] = 우하단 세모가 유지되지 않은 경우(마름모에 포함됨)
        // dp[i][1] = 우하단 세모가 유지되어 이후 사용 가능한 경우
        int[][] dp = new int[n+1][2];
        
        dp[0][0] = 0;
        dp[0][1] = 1;
        
        for(int i=1;i<=n;i++){
            // 우하단 세모가 마름모에 포함된 경우는 이전 가능성과 동일한 가능성으로 넘어오므로 둘을 더해준 합이된다.
            dp[i][0]= (dp[i-1][0] + dp[i-1][1]) %10007;
            // 위쪽에 정사각형이 붙은 경우(tops[i-1]==1) 와 그렇지 않은 경우를 파악해 준다.
            dp[i][1]= (tops[i-1]==1 ? 2*dp[i-1][0] + 3 * dp[i-1][1] : dp[i-1][0] + 2 * dp[i-1][1])%10007 ;
        }
        answer = (dp[n][0] + dp[n][1])%10007;
        return answer;
    }
}