해당 게시글에서는 [백준] 10844 쉬운 계단 수 문제를 해설하고 Python을 이용하여 풀고자 한다.
🤔 접근법
문제 풀이 방식을 빠르게 알고싶다면 💡문제 풀이 부분 부터 봐주세요 :)
10844 문제는 DP(다이나믹 프로그래밍)에 대한 문제로 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법하는 방식의 알고리즘이다.
문제 접근 방식은 유사한 DP 문제를 많이 풀어봐서 그다지 어렵지 않았다. 다른 때와 똑같이 규칙을 찾기위해 N에 따른 값들을 분석했다.
N이 1인 경우와 2인 경우를 나열해보면 어렵지 않게 규칙을 찾을 수 있다.
- N이 1인 경우: 1, 2, 3, 4, 5, 6, 7, 8, 9
- N이 2인 경우: 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98
위의 N이 2인 경우의 10과 12는, N이 1인 경우인 1에서 차이가 1이 나는 숫자들을 뒤에 이어붙인 것이다.
21와 23, 32와 34도 동일하게 각각 2와 3에 차이가 1인 숫자를 연달아 붙인 것이다.
즉 계단수를 만들기 위해서는 이전 계단수의 일의 자리 숫자에 +1, -1한 숫자를 맨 끝에 붙여주면 된다. 따라서 다음 N에서는 계단수가 2배가 되는 것을 알 수 있다.
하지만 여기서 주의해야 할 점은 0과 9 같이 경계값에서는 계단수가 2개가 아닌 1개만 생성된다는 것이다.
처음엔 이전 계단수를 2배한 뒤, 끝이 0과 9인 것의 개수를 빼주려고 했다. 하지만 끝이 0과 9인 것의 개수를 세주는 과정이 쉽지 않았다. (이 방법으로도 풀 수 있을 거 같은데… 혹시나 아신다면 알려주세요!)
그래서 새로운 방법을 생각하다가 든 생각이 끝자리가 i인 계단수의 개수는 얼마지?였다. 끝자리가 i가 되기 위해서는 이전 길이에서의 끝자리가 i-1, i+1이면 된다.
즉 길이가 N일 때 일의 자리가 i인 계단수의 개수는, 길이가 N-1일 때 일의 자리가 i-1, i+1인 계단수의 개수를 각각 합한 것이다. 해당 아이디어만 있다면 이제 구현은 어렵지 않다.
💡 문제 풀이
길이가 N인 계단수를 일의 자리 숫자에 따라 배열에 분리해보자. 예를 들면 N이 1일 때 계단수는 1~9가 있으므로 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]로 정하는 것이다. (계단수 중에서는 일의 자리가 0인 것도 있으므로 0에 대한 인덱스도 만들어 줘야 한다.)
그렇다면 N이 2일 때 계단수의 배열은 어떻게 될까?
위에서 길이가 N일 때 일의 자리가 i인 계단수의 개수는, 길이가 N-1일 때 일의 자리가 i-1, i+1인 계단수의 개수를 각각 합한 것이라고 했으므로, N이 2일 때 인덱스 i에서의 계단수는 arr[1][i-1]+arr[1][i+1]이 된다.
모든 인덱스에 대해 계산해주면 N이 2일 때의 배열은 [1, 1, 2, 2, 2, 2, 2, 2, 2, 1]이 된다.
이를 일반화 한 식은 다음과 같다.
- dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1]
아직 이해가 되지 않았다면, 위 식의 N과 i에 숫자를 대입하여 아래 표와 비교해보길 바란다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| dp[1] | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| dp[2] | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
| dp[3] | 1 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 3 | 2 |
| dp[4] | 3 | 4 | 7 | 7 | 8 | 8 | 8 | 8 | 7 | 6 | 3 |
📂 코드
이제 구현만 남았다. 하지만 위 식을 그대로 이용해 코드를 짠다면 에러가 발생할 것이다. 아직 0과 9일 때의 예외처리를 하지 않았기 때문이다.
일의 자리가 0일 때는 오로지 1에서부터, 일의 자리가 9일 때는 오로지 8에서부터 계단수가 만들어진다. 따라서 dp[N][0] = dp[N-1][1], dp[N][9] = dp[N-1][8]이다.
필자는 인덱스가 0과 9일 때를 for문 따로 빼주고 위 식처럼 대입했다.
N번째 배열을 만들기 위해서는 N-1번째 배열만 있으면 된다. 위 식을 그대로 사용하면 N에 따라 모든 배열을 만들어 줘야 하므로 메모리 낭비가 심할 것이라고 생각했다.
따라서 이전 값을 따로 저장해두고 dp 배열을 이전 배열에 따라 갱신하는 형태로 코드를 구현했다.
1
2
3
4
5
6
7
8
9
N = int(input())
dp = [0]+[1]*9
for _ in range(N-1):
prev = dp[:] # 이전 dp 복사
dp[0] = prev[1]
for i in range(1, 9):
dp[i] = prev[i-1]+prev[i+1]
dp[9] = prev[8]
print(sum(dp)%1000000000)