[파이썬] 프로그래머스 : 산 모양 타일링 (레벨3)

[파이썬] 프로그래머스 : 산 모양 타일링 (레벨3)

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

---

풀이

방향성 생각

• 유명한 타일링 DP. 개꿀문제
• 각 지점에 대해서 가능한 경우의 수를 DP로 채운다.
• 점화식을 찾아서 바텀업으로 풀이.
  • 탑다운으로 풀기에는 바로 분할해서 보기 쉽지 않다.
  • 이전 타일 상태에서 경로만 지정해주면 바텀업이 쉽다.
• $N=4$, $tops=[1,1,0,1]$의 경우에는 DP 테이블을 다음과 같이 나타낼 수 있다.
  • 0 1 0 1 0 0 0 1 0
  • 1 1 1 1 1 1 1 1 1
  • 1은 타일이 깔린 부분, 0은 타일이 없는 부분
• 초기 상태 DP를 채워보면
  • 0 3 ? ? ? ? ? ? ?
  • 1 2 * ? ? ? ? ? ?
• CASE1) 2 옆의 아래쪽 타일을 채워보자.
  • 1에서 2칸짜리 타일을 붙이는 경우 1가지
  • 2,3에서 1칸짜리 타일을 붙이는 경우 1가지
  • Node1 + (Node2 or Node3 : Tops의 유무에 따라 다르다)
  • 0 3 ? * ? ? ? ? ?
  • 1 2 4 * ? ? ? ? ?
• CASE2) 4 옆에있는 아래쪽 타일을 채워보자.
  • Node2 or Node3에서 한칸짜리 타일 2개 or 두칸짜리 타일 1개를 붙인다.
  • 또는 Node4에서 한칸짜리 타일 1개를 깔면 된다.
  • 여기서 2칸까지 채운 2,3 상태에서 한칸짜리 타일을 2개 까는 것 = 3칸까지 채운 4 상태에서 한칸짜리 타일 1개를 까는 것. -> 중복이 발생한다.
  • (Node2 or Node3 큰 값 : Tops 유무에 따라 다르다)*2 + (Node4)
  • 0 3 ? * ? ? ? ? ?
  • 1 2 4 7 ? ? ? ? ?
• CASE3) 7 위에 있는 타일을 채워보자
  • Node4에서 한칸짜리 타일을 위로 두개 or 두칸 짜리 타일을 위 방향으로 1개
  • 혹은 (Node2 or Node)3에서 두칸짜리 타일을 아래에 깔고, 한칸짜리 타일을 위에
  • (Node2 or Node3 큰 값 : Tops 유무에 따라 다르다) + Node4 *2
  • 0 3 ? 11 ? ? ? ? ?
  • 1 2 4 7 ? ? ? ? ?

 

---

전체코드

def solution(n,tops):

    mod = 10007
    dp = [[0]*(2*n+1) for _ in range(2)]
    dp[0][0] = 1
    dp[0][1] = 2
    dp[1][1] = 3 if tops[0] else 0
    for i in range(2,2*n+1):

        if i%2==0:
            dp[0][i] = sum([dp[0][i-2],
                            dp[1][i-1] if tops[i//2-1] else dp[0][i-1]])%mod
        else:
            dp[0][i] = sum([dp[0][i-1],
                            dp[1][i-2] if tops[i//2-1] else dp[0][i-2]])%mod
            if tops[i//2]:
                dp[1][i] = sum([2*dp[0][i-1],
                                dp[1][i-2] if tops[i//2-1] else dp[0][i-2]])%mod

    return dp[0][-1]

코멘트

• ez