Lv.3 산 모양 타일링 [JAVA]

문제 링크

걸린 시간(성공 여부): 1시간 (실패)

아이디어

처음에 뒤집혀있는 삼각형 기준으로 dp를 사용해야 겠다는 생각은 했으나
그다음부턴 점화식을 못짜겠어서 포기했었는데 풀이를 보고 푸니 새삼 너무 겁먹은 듯 하다.

핵심은 열 i까지 덮었을 때 오른쪽 끝이 마름모로 튀어나와서 다음 열로 이어져야 하는 상태(dp1) 인지,
아니면 딱 닫혀 있는 상태(dp2) 인지를 나눠서 생각하는 것.

• dp1[i]: 열 i까지 덮었을 때 오른쪽 끝이 마름모로 튀어나와 있는 경우
• dp2[i]: 열 i까지 덮었을 때 깔끔하게 닫혀 있는 경우

그리고 i열 꼭대기에 삼각형이 붙어 있는지(tops[i-1]) 여부에 따라 경우의 수가 달라짐.

점화식은 다음과 같이 됨:

• dp1[i] = dp1[i-1] + dp2[i-1]
  (이전이 어떤 상태든 i열에서 마름모 하나만 오른쪽으로 빼주면 됨)

• dp2[i]는 꼭대기 여부에 따라 다름

  • tops[i-1] == 0 → dp2[i] = dp1[i-1] + 2*dp2[i-1]
    (미결합 받아서 닫는 경우 1 + 내부에서 닫는 경우 2)
  • tops[i-1] == 1 → dp2[i] = 2*dp1[i-1] + 3*dp2[i-1]
    (미결합 받아서 닫는 경우 2 + 내부에서 닫는 경우 3)

초기값은

• dp1[1] = 1
• dp2[1] = tops[0] == 0 ? 2 : 3

마지막에 (dp1[n] + dp2[n]) % 10007이 답.(이거 모듈러 연산 안해줘서 틀렸다가 다시 제출함)

풀이 코드

import java.util.*;

class Solution {
    public int solution(int n, int[] tops) {
        int [] dp1 = new int [n+1];//3번 마름모
        int [] dp2 = new int [n+1];//그 외에 모양
        dp1[1] = 1;
        dp2[1] = tops[0]==0? 2:3;
        for(int i=2; i<=n; i++){
            dp1[i] = (dp1[i-1]+dp2[i-1])%10007;
            dp2[i] = tops[i-1]==0? (dp1[i-1]+2*dp2[i-1])%10007:(2*dp1[i-1]+3*dp2[i-1])%10007;
        }
        return (dp1[n]+dp2[n])%10007;
    }
}