[백준 11057] 오르막 수

문제 출처 : https://www.acmicpc.net/problem/11057

 

간단한 DP 문제 입니다. 점화식이 바로 떠오른다면 문제 없지만 보통 점화식을 바로 떠올릴 수 없습니다. 그런 경우 Top-Down으로 먼저 문제를 해결하고 이를 Bottom-Up으로 바꾸는 것이 좋습니다.

아직 Top-Down, Bottom-Up이 무엇인지 잘 모르겠다면 아래 링크를 통해 확인해 보시기 바랍니다.

https://wikidocs.net/206429

09. 동적 계획법(다이나믹 프로그래밍)

 

문제 이해하기

Top-Down으로 문제를 해결하기 위해 어떤식으로 구현할 지 생각해 보겠습니다. 결국 오르막 수를 구하기 위해서 가장 중요한 것은 마지막 숫자가 무엇인지 입니다. 예를 들어 3자리 숫자들 중 2으로 끝나는 오르막수를 구한다고 하겠습니다.

1. 2자리 숫자들 중 0으로 끝나는 오르막 수의 개수
2. 2자리 숫자들 중 1로 끝나는 오르막 수의 개수
3. 2자리 숫자들 중 2로 끝나는 오르막 수의 개수

위 세가지를 더해주면 3자리 숫자들 중 2로 끝나는 오르막 수의 개수를 구할 수 있습니다.

좀 더 쉽게 이해하기 위해 각각의 숫자들을 생각해 보겠습니다. 2자리 숫자들 중 0으로 끝나는 오르막 수는 00 입니다. 여기에 2를 붙여 002 만드는 것입니다. 다음으로 2자리 숫자들 중 1로 끝나는 오르막 수는 01, 11 입니다. 여기에 2를 붙이면 012, 112가 됩니다. 마지막으로 2자리 숫자들 중 2로 끝나는 오르막 수는 02, 12, 22 입니다. 여기에 2를 붙이면 022, 122, 222가 됩니다. 위 세가지 경우를 모두 더하면 6가지가 됩니다.

즉 N자리 숫자들의 오르막 수를 구하기 위해서는 N - 1자리 숫자들 중 0으로 끝나는 오르막 수부터 N - 1자리 숫자들 중 9로 끝나는 오르막 수의 모든 합계입니다.

코드 작성하기

문제를 이해했으니 코드를 작성해 보겠습니다.

입력 받기

N = int(input())

몇 자리 숫자인지 알 수 있는 수의 길이 N을 입력 받습니다.

Top-Down 1

먼저 간단하게 뼈대가 되는 로직을 확인해 보겠습니다.

mod = 10_007
def solve(n, c):
    ans = 0
    for i in range(c + 1):
        ans += solve(n - 1, i)
        ans %= mod
    return ans

print(solve(N, 9))

위에서 언급한 것처럼 N - 1번째 자리 숫자들 중 c보다 작은 숫자로 끝나는 경우의 수를 모두 더해준 것입니다. c값은 가장 큰 수인 9입니다. 그럼 각각 0부터 9까지 모든 오르막 수의 합계를 구할 수 있습니다. 그리고 문제에서 언급했듯이 10,007로 나눈 값을 저장합니다.

Top-Down 2

위의 로직은 뼈대만 있는 것으로 종료 조건과 메모이제이션 처리가 전혀 되어 있지 않습니다. 종료 조건과 메모이제이션 로직을 추가해 보겠습니다.

dp = [[0] * 10 for _ in range(N + 1)]
def solve(n, c):
    if n == 0:
        dp[n][c] = 1
        return 1

    if dp[n][c]:
        return dp[n][c]
    
    ans = 0
    for i in range(c + 1):
        ans += solve(n - 1, i)
        ans %= mod
    dp[n][c] = ans
    return ans

print(solve(N, 9))

n 값이 0일 때 1을 리턴합니다. 숫자가 몇이건 한자리 수의 오르막수는 1개 입니다. 따라서 무조건 1을 리턴하는 것입니다. 다음으로 메모이제이션 로직을 추가하였습니다.

추가적으로 Bottom-Up까지 작성해 볼까 했는데 다행이 Top-Down으로 문제가 해결되었습니다. 각자 Bottom-Up 로직도 작성해 보시기 바랍니다.