[백준/DP/10844] 쉬운 계단 수

이미지 클릭시, 문제로 이동됩니닷 :)

문제가 짧다고 쉬울거라고 생각이 든다면 경기도 오산이다.

이해하기가 어려웠다.

1. 입력 받은 N을 자리수로 생각한다.

2. 인접한 숫자간 차이는 1이다.

위 두가지를 기준으로 생각해야한다. 첫째 줄 N... 너무 헷갈렸다.

n=1 일 때, 한 자리수로 만들 수 있는 계단수

1,2,3,4,5,6,7,8,9  

계단수는 총 9개이다.

n=2 일 때, 두 자리수로 만들 수 있는 계단수

1:  
    1을 기준으로 : 10, 12  
2:  
    2를 기준으로 : 21, 23  
3:  
    3을 기준으로 : 32, 34  
4:  
    4를 기준으로 : 43, 45  
5:  
    5를 기준으로 : 54, 56  
6:  
    6을 기준으로 : 65, 67  
7:  
    7를 기준으로 : 76, 78  
8:  
    8를 기준으로 : 87, 89  
9:  
    9를 기준으로 : 98

계단수는 총 17개이다.

n=3 일 때, 세 자리수로 만들 수 있는 계단수

1: 10, 12,  
    10을 기준으로 : 101,  
    12를 기준으로 : 123, 121  
2: 21, 23  
    21을 기준으로 : 210, 212  
    23을 기준으로 : 232, 234  
3: 32, 34  
    32를 기준으로 : 321, 323  
    34를 기준으로 : 343, 345  
4: 43, 45  
    43을 기준으로 : 432, 434  
    45를 기준으로 : 454, 456  
5: 54, 56  
    54를 기준으로 : 543, 545  
    56을 기준으로 : 565, 567  
6: 65, 67  
    65를 기준으로 : 654, 656  
    67를 기준으로 : 676, 678  
7: 76, 78  
    76을 기준으로 : 765, 767  
    78을 기준으로 : 787, 789  
8: 87, 89  
    87을 기준으로 : 876, 878  
    89를 기준으로 : 898  
9: 98  
    98를 기준으로 : 989, 987

 

계단수는 총 32개이다.

문제에서 구하고자 하는 계단수는 끝 자리의 값을 기준으로 +1,-1 한 값이다.
끝자리가 3이라면 2 또는 4, 끝자리가 2라면 1 또는 3이다.

 

import sys
input = sys.stdin.readline

N = int(input())
dp = [[0]*10 for i in range(N+1)]

# n=1 일 때 1로 초기화
for i in range(1,10):
  dp[1][i] = 1

for j in range(2,N+1):
  # 0부터 9까지 반복하면서 값을 넣어준다.
  for k in range(10):
    if k==0:
      dp[j][k] = dp[j-1][1]
    elif k==9:
      dp[j][k] = dp[j-1][8]
    else:
      dp[j][k] = dp[j-1][k-1] + dp[j-1][k+1]

print(sum(dp[N]) % 1000000000)

 

위 코드의 점화식은 아래와 같다.

 

dp[자리수][앞숫자] = dp[자리수-1][앞숫자-1] + dp[자리수-1][앞숫자+1]

 

문제가 진짜 너무너무너무너무 어려웠다.
이 문제는 풀었다기 보다는 이해했다가 맞을 것 같다.

1. 로밍맨님의 유튜브 강의
2. 코택님의 블로그글

을 정독, 정독 또 정독하였다. 

 

이 문제 때문에 블로그에 방문했다면 위 두 링크도 확인하면 좋을 것 같다.