백준 #10844 쉬운 계단 수 (파이썬)

문제 링크

알고리즘 분류가 다이나믹 프로그래밍인 문제들을 풀다가 발견한 문제.

Try #1: 점화식 찾아보기

# 길이가 N인 계단 수
# 0으로 시작하는 건 제외

# N=1 : 1,2,3,4,5,6,7,8,9
# N=2 : 10,12 / 21,23 / 32,34 / 43,45 / 54,56 / 65,67 / 76,78 / 87,89 / 98

N = int(input())

dp = [0] * (N+1)
dp[1] = 9

for i in range(2, N+1):
    dp[i] = 2 * dp[i-1] - 1
print(dp[N] % 1000000000)

N = 1일 때부터 계단수 생성 과정을 대충 나열해보았는데, 2k+1 씩 커지는 것 같아서 제출해보았는데 역시나 틀렸다.

Try #2: 어디는 2개, 어디는 1개가 생기는가?

다이나믹 프로그래밍이라서 dp 배열을 어떻게 만들어야 할지 고민하고 있던 찰나, 원리부터 먼저 이해해보자는 생각이 들었다.

그 결과, n-1자리 계단수에서

• 끝이 0이나 9인 경우 -> n자리 계단수 1개를 생성한다.
• 그 외의 경우 -> n자리 계단수 2개를 생성한다.

라는 원리를 파악하였다.

그리고 n자리 계단수 정보를 찾는 과정에 n-1자리 계단수 정보만 필요하지, n-2 이하 자리의 계단수 정보가 필요한 것은 아니므로 굳이 dp 배열에 누적하여 메모이제이션할 필요가 없었다.

N = int(input())

arr = [1] * 10
arr[0] = 0

for _ in range(2, N+1):
    tmp = [0] * 10
    tmp[0] = arr[1]
    tmp[1] = arr[0] + arr[2]
    tmp[2] = arr[1] + arr[3]
    tmp[3] = arr[2] + arr[4]
    tmp[4] = arr[3] + arr[5]
    tmp[5] = arr[4] + arr[6]
    tmp[6] = arr[5] + arr[7]
    tmp[7] = arr[6] + arr[8]
    tmp[8] = arr[7] + arr[9]
    tmp[9] = arr[8]
    arr = tmp
print(sum(arr) % 1000000000)

arr, tmp에는 끝자리가 0부터 9까지의 계단수 개수를 저장한다.

tmp[1]에서 tmp[8]까지는 range로 묶을 수도 있다.
가독성이 이게 더 좋아보여서 이렇게 썼을 뿐이다.