📊 계단 수 문제의 동적 계획법 접근과 해결 전략
계단 수 문제는 인접한 자릿수의 차이가 정확히 1인 특별한 수열을 계산하는 문제입니다. 이 보고서에서는 백준 10844번 문제의 효율적인 해결 방법과 동적 계획법을 활용한 접근 방식을 상세히 분석해보겠습니다.
1. 🔍 계단 수의 정의와 특성
계단 수는 인접한 모든 자리의 차이가 정확히 1인 수를 의미합니다. 예를 들어 45656은 계단 수입니다.
- 4와 5의 차이는 1
- 5와 6의 차이는 1
- 6과 5의 차이는 1
- 5와 6의 차이는 1
1.1. 계단 수의 패턴 분석
계단 수를 만들기 위해서는 이전 자릿수의 값에 따라 다음에 올 수 있는 숫자가 제한됩니다3:
- 이전 자릿수가 0인 경우: 다음에는 1만 올 수 있음
- 이전 자릿수가 9인 경우: 다음에는 8만 올 수 있음
- 이전 자릿수가 1~8인 경우: 다음에는 이전 숫자보다 1 작거나 1 큰 숫자가 올 수 있음
2. 🧮 문제 해결을 위한 DP 접근법
2.1. 상태 정의와 점화식 설계
이 문제는 전형적인 다이나믹 프로그래밍으로 해결할 수 있습니다58:
dp[i][j] = 길이가 i이고 마지막 숫자가 j인 계단 수의 개수- dp[i] = dp[i-1]1 (0 다음에는 1만 올 수 있음)
- dp[i]9 = dp[i-1]8 (9 다음에는 8만 올 수 있음)
- dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] (1 ≤ j ≤ 8)
2.2. 초기값 설정
3. 💻 구현 전략과 코드 분석
https://www.acmicpc.net/problem/10844
3.1. 메모이제이션 테이블 설계
문제에서 N은 최대 100이므로, 101×10 크기의 2차원 배열이 필요합니다5. 이를 통해 모든 가능한 상태를 저장할 수 있습니다.
# cache[n][d] : 길이 n인 계단 수의 개수, 마지막 자릿수가 d인 경우
cache = [[0] * 10 for _ in range(101)]3.2. 초기값 설정과 점화식 적용
# 초기값
cache[1][0] = 0
for i in range(1, 10):
cache[1][i] = 1
# 점화식
for i in range(2, 101): # 길이 n
for j in range(10): # 마지막 자릿수 d
if j == 0:
cache[i][j] = cache[i-1][1] % MOD
elif j == 9:
cache[i][j] = cache[i-1][8] % MOD
else:
cache[i][j] = (cache[i-1][j-1] + cache[i-1][j+1]) % MOD이 코드는 길이가 2부터 100까지의 모든 계단 수를 계산하며, 각 단계에서 모듈로 연산을 통해 오버플로우를 방지합니다35.
import sys
input = sys.stdin.readline
MOD = 1000000000
# cache[n][d] : 길이 n인 계단 수의 개수, 마지막 자릿수가 d인 경우
cache = [[0] * 10 for _ in range(101)]
# 초기값
cache[1][0] = 0
for i in range(1, 10):
cache[1][i] = 1
# 점화식
for i in range(2, 101): # 길이 n
for j in range(10): # 마지막 자릿수 d
if j == 0:
cache[i][j] = cache[i-1][1] % MOD
elif j == 9:
cache[i][j] = cache[i-1][8] % MOD
else:
cache[i][j] = (cache[i-1][j-1] + cache[i-1][j+1]) % MOD
ans = 0
n = int(input())
for j in range(10):
ans += cache[n][j]
ans %= MOD # 파이썬은 굳이 안해도 되지만 다른 언어에선 오버플로우 방지
print(ans)4. 📝 구체적인 예시 분석
4.1. 길이가 1인 계단 수 (N=1)
길이가 1인 계단 수는 1부터 9까지 총 9개입니다28.
4.2. 길이가 2인 계단 수 (N=2)
길이가 2인 계단 수는 다음과 같습니다8:
- 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98
총 17개의 계단 수가 있습니다. 이는 다음과 같이 계산됩니다:
- dp2 = dp11 = 1 (10)
- dp21 = dp1 + dp12 = 0 + 1 = 1 (21)
- dp22 = dp11 + dp13 = 1 + 1 = 2 (12, 32)
- …
- dp29 = dp18 = 1 (98)
5. 🔄 최적화와 주의사항
5.1. 모듈로 연산의 중요성
문제에서 요구하는 대로 결과값을 1,000,000,000으로 나눈 나머지를 구해야 합니다2. 이는 숫자가 매우 커질 수 있기 때문에 오버플로우를 방지하기 위함입니다.
MOD = 1000000000
# 계산 과정에서 매번 모듈로 연산 적용
cache[i][j] = (cache[i-1][j-1] + cache[i-1][j+1]) % MOD5.2. 시간 및 공간 복잡도
6. 🎯 결론
계단 수 문제는 다이나믹 프로그래밍의 전형적인 예시로, 상태 정의와 점화식을 올바르게 설계하는 것이 핵심입니다. 이 문제에서는 길이와 마지막 자릿수를 상태로 정의하여 모든 가능한 계단 수를 효율적으로 계산할 수 있었습니다.
DP 문제를 해결할 때는 항상 다음 단계를 따르는 것이 중요합니다:
- 문제를 부분 문제로 나누고 상태를 정의한다
- 부분 문제 간의 관계를 나타내는 점화식을 설계한다
- 초기값을 설정한다
- 테이블을 채워나가며 최종 해를 구한다
이러한 접근법은 다양한 DP 문제에 적용할 수 있는 일반적인 패턴이므로, 유사한 문제를 해결할 때 참고할 수 있습니다79.
Citations:
- https://www.acmicpc.net/problem/10844
- https://www.acmicpc.net/problem/10844
- https://velog.io/@iamjinseo/%EB%B0%B1%EC%A4%8010844-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8-%EC%88%98
- https://konkukcodekat.tistory.com/139
- https://velog.io/@minchoul2/%EB%B0%B1%EC%A4%80-10844-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8-%EC%88%98-Python
- https://velog.io/@doorbals_512/%EB%B0%B1%EC%A4%80-10844%EB%B2%88-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8
- https://yabmoons.tistory.com/22
- https://jangkunstory.tistory.com/44
- https://wooono.tistory.com/642
- https://ddiyeon.tistory.com/51
- https://velog.io/@jypapapaa/%EB%B0%B1%EC%A4%80-1562-%EA%B3%84%EB%8B%A8-%EC%88%98
- https://cotak.tistory.com/12
- https://seol-limit.tistory.com/35
- https://www.acmicpc.net/problem/1562
- https://st-lab.tistory.com/134
- https://easycodediary.tistory.com/92
- https://daejipo2837.tistory.com/300
- https://yeons4every.tistory.com/107
- https://togll.tistory.com/300
- https://velog.io/@zeesouth/%EB%B0%B1%EC%A4%80-1562.-%EA%B3%84%EB%8B%A8-%EC%88%98-Java
- https://dbstndi6316.tistory.com/154
