문제 이해 단계
인접한 수(양쪽에 있는 수)랑 차이가 딱 1씩만 나는 수를 계단 수라고 한다.
자릿수 N이 주어질 때, 총 몇 가지 경우의 수가 나오는지 구하는 문제이다.
문제 접근 단계
이 문제를 들었을 때는 전혀 감이 잡히지 않았기 때문에
일단 두 자리 계단수부터 계속 써봤다.
N = 2
10 / 21 / 32 / 43 / 54 / 65 / 76 / 87 / 98
12 / 23 / 34 / 45 / 56 / 67 / 78 / 89
N = 3
101 / 121 / 123 / 212 / 232/ 234 / 343 / 345
454 / 456 / 565 / 567 /... / 898 / 987 / 989
1. 연속적인 숫자가 나타난다.
2. 경우의 수에 영향을 주는 것은 끝자리에 어떤 수가 오느냐이다.
3. 끝자리가 0과 9를 제외한 1~8은 +-1씩 해서 총 2가지씩 경우의 수가 나온다.
1번 특징은 2번 특징의 부분적인 특징, 2번 특징이 1번 특징을 포괄하고 있다.
즉, 2번 특징을 해결하면 자연스럽게 1번 특징이 해결되기 때문에
2번 특징을 좀 더 분석해 보기로 하였다.
2번 특징이 무슨 말이냐면은
만약 N = 3 일 때 즉, 세 자릿수를 구한다고 가정해 보자.
그렇다면 N = 2일 때의 끝자리에 한자리 수를 더 붙이는 건데,
이때 영향을 주는 것은 N = 2일 때의 끝자리 밖에 없다는 뜻이다.
예를 들어, 10이란 수가 이미 있고,
여기서 N = 3일 때의 계단수를 만든다고 가정해 보면,
0이란 수와 1 차이가 나는 101밖에 안 되는 것이다.
만약 12라면 2에 영향을 받아 123,121이 두 수밖에 안되듯이 말이다.
3번 특징으로는 0과 9를 제외한 1~8은 +-1씩 해서 총 2가지씩 경우의 수가 나온다.
이 특징을 자세히 분석하기 위해 3가지 케이스로 나눠보기로 하였다.
Case 1. 끝자리가 0
Case 2. 끝자리가 1 ~ 8
Case 3. 끝자리가 9
Case1 끝자리가 0인 경우
가능한 계단수는 다음에 1이 오는 01로 하나밖에 없다.
Case 2인 경우
끝자리가 x라고 하면 x+1, x-1인 2개가 있다.
Case 3인 경우
Case1가 마찬가지로 8 하나밖에 없다.
위 특징이 일반화 가능할까?
N=1일 때부터 한번 해보면 된다.
일단 일반화를 위해서 배열을 하나 만들어보도록 하자
. DP [a][b] = c라는 2차원 dp 배열을 만들었는데,
'길이가 a이고 끝자리가 b인 계단수의 개수는 c개다.' 뜻이다.
N = 1일 때는 0을 제외한 모든 수가 그 자체로 계단수이기 때문에
DP [1][1~9] = 1이다.
N = 2
Case 1.
N = 1 일 때 1이 오는 경우 즉 DP [1][1] 일 때와 같다.
즉 DP [2][0] = DP [1][1]
Case 2.
끝자리가 4라고 하자. 앞에 오는 것이 가능한 것은 3,5 두 개다.
즉 DP [1][3], DP [1][5]이다. 이는 4의 +-1이므로,
4가 x라고 한다면 x+1, x-1이다. 일반화하면 DP [2][x] = DP [1][x+1] + DP [1][x-1]
Case 3.
Case 1. 과 동일한 경우이다.
N = 1일 때 8이 오는 경우밖에 없기 때문에, 즉 DP [2][9] = DP [1][8]이다.
N = 3
Case 1.
끝자리에 0이 오면 그 이전에 올 수 있는 것은 1이기 때문에
210 앞에 21은 DP [2][1]에 담겨있는 값이다.
즉 DP [3][0] = DP [2][1]이다.
Case 2.
끝자리가 4라고 하자.
앞에 오는 것이 가능한 것이 3, 5 두 개다.
나열해 보면 234 / 434 / 454 / 654이다.
여기서 모두 끝에 4를 빼면 23 / 43 / 45 / 65가 되는데
23 / 43은 DP [2][3]이고 45 / 65는 DP [2][5]이다.
즉, DP [3][4] = DP [2][3] + DP [2][5]
Case 3.
Case 1과 같은 원리이다.끝자리에 9가 오면 그 이전에 올 수 있는 것은 8밖에 없다.
그래서 789/989 두 수가 계단수이다.
9를 뺀 78/98은 DP [2][8]과 같고 따라서
DP [3][9] = DP [2][8]이다.
N = 2, N = 3에서 모두 적용되는 것을 확인했으니
홀수, 짝수 부분에서 모두 적용되는 것을 확인하였다.
어차피 끝자리에 따라 모두 결정되기 때문에
N이 아무리 늘어나도 일반화될 것이다.
굳이 N = 3까지 확인 한 이유는 가시화하여 이해를 돕기 위함이었다.
이제 이 식을 점화식으로 일반화하면 이렇게 된다.
Case 1. 끝자리가 0인 경우 DP [x][a] = DP [x-1][1]
Case 2. 끝자리가 1~8인 경우 Dp [x][a] = DP [x-1][a-1] + DP [x-1][a+1]
Case 3. 끝자리가 9인 경우 DP [x][a] = DP [x-1][8]
이제 위의 식을 코드로 구현하면 모든 풀이는 끝나게 된다.
문제 구현 단계
#include <iostream>
using namespace std;
#define MOD 1000000000;
long long d[101][10];
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N;
cin >> N;
for(int i = 1; i<= 9; i++) d[1][i] = 1;
for(int i = 2; i <= N; i++){
for(int j = 0; j <= 9; j++){
switch(j){
case(0):
d[i][j] = d[i-1][1]% MOD;
break;
case(9):
d[i][j] = d[i-1][8] % MOD;
break;
default:
d[i][j] = (d[i-1][j-1] + d[i-1][j+1]) %MOD;
break;
}
}
}
long long answer = 0;
for(int i = 0; i <= 9; i++) answer += d[N][i];
cout << answer % MOD;
}코드는 사실상 그렇게 길지 않은데, 반복문으로 1~N까지 모두 확인해 주면서
0~9까지의 숫자를 하나씩 모두 확인해 주는 것이다.
확인해 주면서 0과 9는 따로 처리해 준다.
먼저 N = 1일 때는 따로 초기화 해준 다음
스위치문을 사용하여 0, 1~8, 9 일 때를 따로 처리해 주었다.
문제조건에서 1,000,000,000을 나눈 나머지를 구하라고 했으므로
이를 MOD라는 상수로 정의하여 따로 빼줘 계산했다.
우리가 구해야 하는 것은 N자리일 때의 총개수이기 때문에
0~9까지의 전체개수를 다 더해준 것이 답이 된다.
유의해야 할 점은 이 과정에서 또 값이 엄청나게 커져
오버플로우가 발생할 수 있기 때문에 MOD연산을 한번 더 한다.
시행착오
2차원 DP를 처음 접해봤던 것은 아닌데 2차원 DP를 사용해해야 하는지 꿈에도 몰랐다.
그러니까 접근부터 실패했던 문제라고 해야 하는 게 맞는 것 같다.
인터넷에 있는 풀이를 참고했는데,
이해하는데만 해도 시간이 꽤 걸린 것 같다.
이 문제에서 약간의 벽을 느낀 것 같다.
2차원 DP의 벽을 만난 기분이다. 이게 실버라니 어렵다.
그래도 DP는 많이 푸는 사람이 잘 푸는 거라고 했으니까
포기하지 않고 많이 해봐야겠다.