[파이썬] 백준 18244 : 변형 계단 수 (골드3)

[파이썬] 백준 18244 : 변형 계단 수 (골드3)

18244번: 변형 계단 수

---

문제

---

풀이

0. 방향성 생각

• 상태가 5개로 나뉜다.
• 시작 상태 : 증감 구분이 안돼있음
• 1개 연속 증가 : 시작상태에서 오거나 감소상태에서 오는경우
• 2개 연속 증가 : 1개 연속 증가에서 또 증가
• 1개 연속 감소 : 시작상태에서 오거나 증가상태에서 오는경우
• 2개 연속 감소 : 2개 연속 감소에서 또 감소

1. 입력

n = int(input())
dp = [[[0]*10 for _ in range(n)] for _ in range(5)]
dp[0][0] = [1]*10
k = 10**9+7
# dp[state][stage][num]

•  

2. DP 테이블 업데이트

for stage in range(n-1):
    for state in range(5):
        for num in range(10):
            
            if 1<=state<=2 and 1<=num<=9: # 1~9는 0~8에서 증가
            
                if state == 1:
                    for i in (0,3,4):
                        dp[1][stage+1][num] += dp[i][stage][num-1]%k
                if state == 2:
                    dp[2][stage+1][num] += dp[1][stage][num-1]%k

            if 3<=state<=4 and 0<=num<=8: # 0~8은 1~9에서 감소
            
                if state == 3:
                    for i in (0,1,2):
                        dp[3][stage+1][num] += dp[i][stage][num+1]%k #
                if state == 4:
                    dp[4][stage+1][num] += dp[3][stage][num+1]


print(sum(sum(dp[i][-1]) for i in range(5))%k)

 

 

• dp[state][stage][num]로 생각한다. state를 숫자로 바꿔서 생각하면
  1은 0 3 4에서 오고
  2는 1에서
  3은 0 1 2에서오고
  4는 3에서 오고

 

---

전체코드

n = int(input())
dp = [[[0]*10 for _ in range(n)] for _ in range(5)]
dp[0][0] = [1]*10
k = 10**9+7

for stage in range(n-1):
    for state in range(5):
        for num in range(10):
            
            if 1<=state<=2 and 1<=num<=9:
            
                if state == 1:
                    for i in (0,3,4):
                        dp[1][stage+1][num] += dp[i][stage][num-1]%k
                if state == 2:
                    dp[2][stage+1][num] += dp[1][stage][num-1]%k

            if 3<=state<=4 and 0<=num<=8:
            
                if state == 3:
                    for i in (0,1,2):
                        dp[3][stage+1][num] += dp[i][stage][num+1]%k
                if state == 4:
                    dp[4][stage+1][num] += dp[3][stage][num+1]

print(sum(sum(dp[i][-1]) for i in range(5))%k)

 

코멘트

계단수를 비트마스킹으로 접근 안한 사람이라면 난도 자체는 비슷하게 느껴질듯?