문제링크
https://www.acmicpc.net/problem/10844
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
조건
- 시간 제한 : 1s
- 메모리 제한 : 256MB
해설
앞에서 선택한 숫자와 1 차이가 나는 숫자를 연속해서 고르는 방법의 수를 구하면 된다. 이를 일반항을 구하여 해결하는 것보다는 DP를 통해 직접 값을 구하는 방법이 더 쉽다.
풀이
9 → 17 → 32 → 61 → ... 에서 규칙을 찾아보려다 실패했다. ㅋㅋㅋ
처음에는 항이 늘어날 때의 개수에 대한 규칙을 찾아 더하기나 곱하기로 계산을 하려 했는데, 곰곰히 생각해보니 직접 방법의 수가 증가하는 걸 계산하는 편이 더 빠르고 편리할 것 같아서 DP로 풀어보았다.
0 : 0 1 1 3
1 : 1 1 3 4
2 : 1 2 3 7
3 : 1 2 4 7
4 : 1 2 4 8
5 : 1 2 4 8
6 : 1 2 4 8
7 : 1 2 4 7
8 : 1 2 3 6
9 : 1 1 2 3
N - 1 2 3 4
Sum : 9 → 17 → 32 → 61
문제를 쉽게 해결하기 위해서는 위의 형태처럼 2차원 배열을 사용해주어야 한다. 여기에서 N값에 따라 동적으로 배열의 크기가 달라지기 때문에, 벡터 안에 int형 벡터를 담는 2차원 벡터를 사용해주었다.
vector<vector<int>> dp (10, vector<int>(N, 0));
// dp[각 숫자][자리수 N]
N자리수에 대해 각 숫자가 마지막 자리수로 선택될 방법의 수를 적어두었다. 예를 들어, 4자리에서의 3이 선택되는 방법의 경우 _ _ _ 3을 만족하는 계단 수의 수가 7개이다. 위 숫자들의 관계와 계단수라는 특징에서 찾을 수 있는 규칙은 k자릿수의 i는 k-1 자릿수의 i-1, i+1의 방법의 수의 합과 같다는 것이다. (i-1, i+1에서 i를 선택할 수 있으므로 합이 i와 같다.) 코드로 작성하면 아래와 같다.
// dp[숫자][자릿수]
dp[i][k] = dp[i-1][k-1] + dp[i+1][k-1];
N이 1일 때부터 원하는 자리까지 올라가면서 dp를 채우는 코드는 아래와 같이 작성할 수 있다. 0과 9에 대해서는 1과 8에서만 선택할 수 있으므로 예외처리를 해주었다.
for(int k = 1; k < N; k++) {
for(int i = 0; i < 10; i++) {
if(i==0) {
dp[0][k] += dp[1][k-1];
} else if (i < 9) {
dp[i][k] += dp[i-1][k-1];
dp[i][k] += dp[i+1][k-1];
} else {
dp[9][k] += dp[8][k-1];
}
// 나머지를 이용해 계산하라는 조건을 적용
dp[i][k] %= 1000000000;
}
}
위 코드에서는 N=1인 경우를 커버하지 못하므로, 초기값 세팅을 따로 빼내어 해주었다.
// N=1일때의 값 초기화
for(int i = 0; i < 10; i++) {
if(i==0) {
dp[i][0] = 0;
continue;
}
dp[i][0] = 1;
}
N자리에서의 각 숫자를 선택하는 방법의 수를 더하면 원하는 결과를 얻을 수 있다. 여기에서도 나머지에 대한 조건을 적용해주어야 한다.
long result = 0;
for(int i = 0; i <10; i++) {
result += dp[i][N-1];
result %= 1000000000;
}
cout << result;
코멘트
알고리즘 풀이 하는 맛이 이 맛이구나!
이차원 벡터는 이번에 처음 사용해봤다. 조금 복잡한 것 같긴 한데, 이정도는 괜찮지. 범위를 잘 확인하자.
코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<vector<int>> dp (10, vector<int>(N, 0));
// N=1일때의 값 초기화
for(int i = 0; i < 10; i++) {
if(i==0) {
dp[i][0] = 0;
continue;
}
dp[i][0] = 1;
}
// k는 자릿수, i는 0~9
for(int k = 1; k < N; k++) {
for(int i = 0; i < 10; i++) {
if(i==0) {
dp[0][k] += dp[1][k-1];
} else if (i < 9) {
dp[i][k] += dp[i-1][k-1];
dp[i][k] += dp[i+1][k-1];
} else {
dp[9][k] += dp[8][k-1];
}
dp[i][k] %= 1000000000;
}
}
long result = 0;
for(int i = 0; i <10; i++) {
result += dp[i][N-1];
result %= 1000000000;
}
cout << result;
return 0;
}
Uploaded by Notion2Tistory v1.1.0