프로그래머스 코딩테스트 - 산 모양 타일링

문제 설명

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

프로그래머스

해결 방법

아이디어

문제를 보고 생각난 것은 'DP를 사용하면 될 것 같다' 였다. 그래서 규칙을 찾으려 노력했다.

 

우선 삼각형과 마름모로 끝나는 패턴으로 나눌 수 있다.

n = 3 일 때

• 삼각형으로 끝나는 경우의 수 : 2
• 마름모로 끝나는 경우의 수: 1

n = 2일 때

• 삼각형으로 끝나는 경우의 수 : 5
  • (n = 1일 떄 삼각형으로 끝나는 경우의 수 * 2) + (n = 1일 떄 마름모로 끝나는 경우의 수)
• 마름모로 끝나는 경우의 수 : 3
  • (n = 1일 떄 삼각형으로 끝나는 경우의 수) + (n = 1일 떄 마름모로 끝나는 경우의 수)

여기에 윗 변에 삼각형이 추가된다면

• 삼각형으로 끝나는 경우의 수 : 8
  
  • (n = 1일 떄 삼각형으로 끝나는 경우의 수 * 3) + (n = 1일 떄 마름모로 끝나는 경우의 수 * 2)
    
• 마름모로 끝나는 경우의 수 : 3
  • 변하지 않음

이를 배열로 생각해보면 다음과 같다.

• dp[n][0] : dp[n-1][0] * (2 or 3) + dp[n-1][1] * (1 or 2) 
• dp[n][1] : dp[n-1][0] + dp[n-1][1]

코드

function solution(n, tops) {
    const dp = Array.from({length: n + 1}, () => Array.from({length: 2}, () => 0))
    dp[0][0] = 1
    for (let i = 1; i < dp.length; i++) {
        if (tops[i - 1]) {
            dp[i][0] = (dp[i-1][0] * 3 + dp[i-1][1] * 2) % 10007
        } else {
            dp[i][0] = (dp[i-1][0] * 2 + dp[i-1][1]) % 10007
        }
        dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % 10007
    }
    const [n1, n2] = dp.pop()

    return (n1 + n2) % 10007;
}

 

처음에는 결과를 반환할 때에만 나머지를 구했는데 절반 정도의 케이스가 통과하지 못하는 문자게 있었다.

그래서 배열에 저장할 때마다 나머지를 구해서 저장하도록 수정했다.

매번 나머지를 구하지 않으면 크기가 굉장히 커기지 때문에 실패하는 것 같았다.