프로그래머스 [Lv. 3] 산 모양 타일링 {언어 : Python} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

def solution(n, tops):
    MOD = 10007
    bottomDP = [0] * n
    topDP = [0] * n
    bottomDP[0] = 1
    topDP[0] = 2 + tops[0]
    
    for i in range(1, n):
        bottomDP[i] = (bottomDP[i - 1] + topDP[i - 1]) % MOD
        topDP[i] = ((bottomDP[i - 1] * (1 + tops[i])) + (topDP[i - 1] * (2 + tops[i]))) % MOD
        
    return (bottomDP[-1] + topDP[-1]) % MOD

풀이 방법

 

1. 초기화:
   • bottomDP[0]은 1로 초기화한다. 이는 첫 번째 위치에서의 기본 상태를 나타낸다.
   • topDP[0]은 2 + tops[0]으로 초기화한다. 이는 첫 번째 위치에서의 상위 상태를 나타낸니다.
2. 점화식을 사용한 반복 계산:
   • bottomDP[i]는 이전 단계의 bottomDP[i-1]과 topDP[i-1]을 더한 값의 MOD 10007 나머지를 저장한다. 이 값은 i번째 위치의 기본 상태를 나타낸다.
   • topDP[i]는 두 부분으로 계산한다:
     1. 이전 단계의 bottomDP[i-1]에 (1 + tops[i])를 곱한 값.
     2. 이전 단계의 topDP[i-1]에 (2 + tops[i])를 곱한 값.
   • 이 두 값을 더한 후 MOD 10007 나머지를 저장한다. 이 값은 i번째 위치의 상위 상태를 나타낸다.
3. 결과 반환:
   • 마지막 위치에서의 bottomDP와 topDP 값을 더한 후 MOD 10007 나머지를 반환하면 끝!

 

 

느낀점

• 이런 규칙 찾는 거는 천재인 것 같다...