백준 - 10844번 쉬운 계단 수 python 문제풀이 [Hellfer]

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

10844번: 쉬운 계단 수

🔷 알고리즘 분류 - 다이내믹 프로그래밍

난이도 - 실버 1

🔶문제 풀이 - 다이내믹 프로그래밍을 이용한 풀이

n = int(input())

# dp[i][j]: 길이가 i이고 마지막 자릿수가 j인 계단 수의 개수
dp = [[0] * 10 for _ in range(n + 1)]

# 길이가 1인 계단 수는 모두 1개
for i in range(1, 10):
    dp[1][i] = 1

# 길이가 2 이상인 계단 수 계산
for i in range(2, n + 1):
    for j in range(10):
        if j == 0:
            # 마지막 자릿수가 0인 경우, 이전 자릿수는 1이어야 함
            dp[i][j] = dp[i - 1][1]
        elif j == 9:
            # 마지막 자릿수가 9인 경우, 이전 자릿수는 8이어야 함
            dp[i][j] = dp[i - 1][8]
        else:
            # 마지막 자릿수가 1부터 8인 경우, 이전 자릿수의 계단 수 개수 합 구하기
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

# 모든 길이에 대한 계단 수의 합 구하기
answer = sum(dp[n]) % 1000000000

print(answer)

🔶문제 이해하기

1. 입력값이 1일 때, 위의 코드는 다음과 같은 작동 과정을 거칩니다.

2. 입력값을 n에 저장합니다.

 

여기서 입력값이 1이므로 n은 1이 됩니다.

3. dp라는 2차원 리스트를 생성합니다.

 

dp의 크기는 (n+1) x 10이 됩니다.

 

입력값이 1이므로 dp의 크기는 2 x 10이 됩니다.

dp 리스트의 첫 번째 행에는 길이가 1인 계단 수의 개수를 저장합니다. 

 

반복문을 통해 dp [1][i] = 1로 초기화합니다. 

 

이는 길이가 1인 계단 수는 모두 1개라는 뜻입니다.

4. 길이가 2 이상인 계단 수를 계산하기 위해 반복문을 사용합니다.

 

외부 반복문은 i가 2부터 n까지 반복합니다. 내부 반복문은 j가 0부터 9까지 반복합니다.

5. 내부 반복문에서 다음과 같은 조건에 따라 dp [i][j] 값을 계산합니다.

j가 0인 경우: dp [i][j] = dp [i-1][1]로 설정합니다. 즉, 마지막 자릿수가 0인 경우 이전 자릿수는 1이어야 합니다.

j가 9인 경우: dp [i][j] = dp [i-1][8]로 설정합니다. 즉, 마지막 자릿수가 9인 경우 이전 자릿수는 8이어야 합니다.

그 외의 경우: dp [i][j] = dp [i-1][j-1] + dp [i-1][j+1]로 설정합니다. 

 

즉, 마지막 자릿수가 1부터 8인 경우 이전 자릿수의 계단 수 개수의 합을 구합니다.

 

이와 같은 작동과정으로 입력값 n을 받아 코드를 수행합니다.

 

 

입력값이 1일 때, 계단 수를 예시로 들어보겠습니다.

길이가 1인 계단 수는 0부터 9까지의 한 자릿수이므로 총 10개입니다:

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

따라서 입력값이 1일 때, 계단 수의 개수는 총 10개입니다.

 

 

입력값이 2일 때, 계단 수를 예시로 들어보겠습니다.

길이가 1인 계단 수는 0부터 9까지의 한 자릿수이므로 총 10개입니다.

길이가 2인 계단 수는 다음과 같습니다:
10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98

따라서 입력값이 2일 때, 계단 수의 개수는 총 17개입니다.

 

 

입력값이 3일 때, 계단 수를 예시로 들어보겠습니다.

길이가 1인 계단 수는 0부터 9까지의 한 자릿수이므로 총 10개입니다.

길이가 2인 계단 수는 다음과 같습니다:
10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98

길이가 3인 계단 수는 다음과 같습니다:
101, 121, 123, 210, 212, 232, 234, 321, 323, 343, 345, 432, 434, 454, 456, 543, 545, 565, 567, 654, 656, 676, 678, 765, 767, 787, 789, 876, 878, 898, 987, 989

따라서 입력값이 3일 때, 계단 수의 개수는 총 32개입니다.