안녕하세요! 오늘은 파이썬 코딩테스트에서 자주 등장하는 알고리즘 문제 중 하나인 “계단 수 구하기”에 대해 자세히 알아보겠습니다. 이 문제를 통해 동적 프로그래밍의 개념과 문제 풀이 과정을 배워보도록 하겠습니다.
문제 설명
계단 수란 다음의 규칙을 갖는 정수의 수를 말합니다:
- 계단 수는 0에서 9까지의 숫자로 이루어져 있습니다.
- 두 인접한 자리의 숫자는 반드시 1 차이여야 합니다. 즉, 예를 들어 234는 유효하지만 235나 123은 유효하지 않습니다.
- 계단 수의 첫 자리는 0이 될 수 없습니다.
자연수 N이 주어졌을 때, N자리 계단 수의 개수는 얼마인가요? 예를 들어, N이 2일 때는 9개의 계단 수가 가능하며, 이들은 10, 12, 21, 23, 32, 34, 43, 45, 54, 65, 76, 78, 87, 89, 98 총 15개입니다.
입력 형식
첫째 줄에 계단 수의 자릿수 N (1 ≤ N ≤ 100)가 주어집니다.
출력 형식
첫째 줄에 N자리 계단 수의 개수를 1,000,000,000으로 나눈 나머지를 출력합니다.
예제 입력
2
예제 출력
15
문제 해결 전략
이 문제는 동적 프로그래밍을 활용하여 해결할 수 있습니다. 계단 수를 문제의 규칙에 맞춰 분류하고, 각 자리수에 대해 가능한 숫자 조합을 고려하여 결과를 도출해낼 수 있습니다. 이제 구체적인 해결 과정을 살펴보겠습니다.
1단계: 상태 정의
N자리 계단 수를 구하기 위해 DP 배열을 정의합니다. dp[n][k]를 사용하여 길이가 n인 계단 수의 마지막 자리가 k인 경우의 수를 표현합니다. 여기서 n은 자리수, k는 마지막 자리 숫자 (0~9) 입니다.
2단계: 초기 조건 설정
길이가 1인 계단 수는 1부터 9까지의 수입니다. 따라서 dp[1][0] = 0 (0은 첫 자리로 올 수 없고), dp[1][1] = dp[1][2] = ... = dp[1][9] = 1로 설정합니다.
3단계: 점화식 유도
길이 n인 계단 수를 구성하기 위해서는 길이 n-1인 계단 수에서 하나의 숫자를 추가합니다. 마지막 자리가 0이면 1로 이어질 수 있고, 마지막 자리가 9이면 8로 이어질 수 있습니다. 따라서 다음과 같은 점화식을 얻을 수 있습니다:
dp[n][0] = dp[n-1][1] dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1] (1 <= k <= 8) dp[n][9] = dp[n-1][8]
4단계: 최종 결과 계산
N자리의 계단 수는 전체 자리수 0부터 9의 경우의 수를 합한 것으로 구할 수 있습니다. 마지막 결과는 sum(dp[N])로 계산됩니다.
구현
이제 이 모든 논리를 파이썬 코드로 구현해 보겠습니다:
def count_stair_numbers(n):
# 모듈러 연산을 위한 상수
MOD = 1000000000
# DP 테이블 초기화
dp = [[0] * 10 for _ in range(n + 1)]
# 길이가 1일 때
for i in range(1, 10):
dp[1][i] = 1
# DP 테이블 채우기
for i in range(2, n + 1):
dp[i][0] = dp[i - 1][1] % MOD
for j in range(1, 9):
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD
dp[i][9] = dp[i - 1][8] % MOD
# 결과 계산
result = sum(dp[n]) % MOD
return result
# 사용자 입력
n = int(input("N 값을 입력하세요: "))
print(count_stair_numbers(n))
마무리
오늘은 “계단 수 구하기” 문제를 통해 동적 프로그래밍의 기본 개념을 이해하고, 실제로 파이썬 코드를 이용해 문제를 해결하는 과정을 살펴보았습니다. 과정을 통해 알고리즘 문제 해결 능력을 향상시키길 바랍니다. 다음 강좌에서도 또 다른 흥미로운 알고리즘 문제를 다룰 예정이니 기대해 주세요!