[백준 파이썬 10844] 쉬운 계단 수 (실버 1)

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

MOD = 1_000_000_000
# cache[n][d] = 길이가 n, 마지막 숫자가 d인 계단수 개수
cache = [[0] * 10 for _ in range(101)]  # n은 1~100 이므로 101개를 만들고, d는 0~9까지니까 10개를 만든다.
for d in range(1, 10): # cache[1][0] 은 0으로 시작하므로 문제 조건에 따라 0이다.
    cache[1][d] = 1 # 길이가 1이고 자릿수가 0이 아니면 초기값은 1이다.

for N in range(2, 101): # 길이 N이 2~100 이고
    for D in range(10): # 자릿수 D가 0~9일 때를 반복
        if D > 0: # 자릿수가 1~9이면 이전 길이의 전 자릿수의 계단수 개수를 더하고,
            cache[N][D] += cache[N - 1][D - 1]
            cache[N][D] %= MOD

        if D < 9: # 자릿수가 0~8이면 이전 길이의 후 자릿수의 계단수 개수를 더한다.
            cache[N][D] += cache[N - 1][D + 1]
            cache[N][D] %= MOD

        # 따라서 최종적으로 d=0이면 이후 자릿수만, d=9이면 이전 자릿수만, d=1~8이면 전,후 자릿수를 다 더하게 된다.

ans = 0
n = int(input())
for d in range(10):
    ans += cache[n][d]
    ans %= MOD

print(ans)

2023.01.11 때 복습한 코드. 

 

문제를 인강 들으면서 복습하는 김에 글도 수정한다.  역시 돈이 좋구나 이해가 확 된다. 

 

DP 문제인데, 우선 cache[n][d]를 계단수 길이가 n이고 마지막 숫자가 d일 때의 경우의 수라고 정의를 하고, n은 1부터 100까지니 101을, d는 자릿수이므로 0~9까지니까 10개로 배열을 만든다. 

 

문제에서 0으로 시작하는 수는 계단수가 아니라고 했으므로 n=1이고 d=0일 때의 경우의 수는 0, d=1~9는 1로 초기값 설정을 해준다. 

그 이후로 n=2~100일 때의 경우를 차례대로 구해주면, d가 0이면 n-1 계단수의 d는 1일 때밖에 안 되고, d가 9이면 n-1 계단수의 d는 8일 때밖에 안 되므로 각각 D > 0, D < 9 로 조건을 나눠서 더해주었다. 

 

마지막으로 n일 때의 d=0~9값을 다 더해주면 답이 나온다. 

 

 

---

2022.11.22 때 작성했던 코드. 

n = int(input())

arr = [ [0] * 10 for _ in range(n+1) ]

for number in range(1, 10): # number는 0부터 9까지.
    # 1번째 자릿수(제일 높은 수)의 1부터 9까지는 1로 저장, 0은 앞에 올 수 없으니 0으로 저장.  
    arr[1][number] = 1 

for digit in range(2, n+1): # 2번째 자릿수부터 n번째 자릿수(1의 자리)까지 반복. 
    for number in range(10): # 각 자릿수에서 0부터 9까지 반복 
        if number == 0: # 0의 계단수는 이전 자릿수(10배한 자릿수)의 1밖에 없다. 
            arr[digit][number] = arr[digit-1][1]
        elif number == 9: # 9의 계단수는 이전 자릿수의 8밖에 없다. 
            arr[digit][number] = arr[digit-1][8]
        else: # 나머지인 1~8의 계단수는 이전 자릿수의 전후의 합과 같다. 
            arr[digit][number] = arr[digit-1][number-1] + arr[digit-1][number+1]
print(arr)
print(sum(arr[n]) % 1000000000)

 

문제명이 쉬운 계단수인데 전혀 닉값을 못하는 문제였다.. 

 

먼저 2차원 배열을 만들고 한 줄에 10개 요소가 있는 것은 각 자릿수에서 0부터 9까지를 나타내며, 이때의 배열값은 계단수의 경우의 수가 들어가게 된다. 

 

arr[자릿수(digit)][각 자릿수에 들어올 수 있는 한 자릿수인 0~9까지의 요소(number)] = 특정 자릿수의 숫자가 m일 때의 계단수의 경우의 수 

 

먼저 자릿수가 1이면 가장 높은 자릿수를 뜻한다. 계단수 길이(n)가 2라면 digit = 1 은 10의 자리, digit = 2 는 1의 자리를 뜻함. 

 

근데 계단수가 0으로 시작 못하니까 arr[1][0] 은 항상 0이 된다. 그리고 왜인진 모르겠지만 첫 번째 예제에서 n=1이면 출력이 9이므로 arr[1][1~9] = 1임을 알 수 있다. 

 

그리고 digit = 2 일 때는 digit - 1의 위아래 숫자(number)의 경우의 수를 합하면 된다.

arr[digit][number] = arr[digit-1][number-1] + arr[digit-1][number+1]

다만 예외로 number = 9의 경우는 이전 digit의 number=8만 계단수니까

arr[digit][9] = arr[digit-1][8] 이 된다. 

 

이제 계단수 길이일 때의 arr[digit = n] 의 각 요소의 합을 구하면 총 경우의 수가 된다. 출력은 나머지로 하라했으니 해주면 끝!