[백준 알고리즘] 10844번: 쉬운 계단 수
May 05, 2020
10844번: 쉬운 계단 수
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.접근 방법:
- 동적 프로그래밍으로 푼다.
- N = 1 에 대한 갯수는 9이다.
- 따라서 차원 배열 dp를 만들고 각 행은 N, 각 열은 뒤에 해당 수의 마지막 숫자를 의미하도록 한다. -> dp[N][10] 사이즈의 배열을 만들면 될 것이다.
- dp[i][j]는 두가지 경우의 수로 만들어 질 수 있는데, 문제에서 주어진 규칙에 따라 마지막 자릿수의 -1이거나 +1인 경우이다.
- 따라서 dp[i][j] 가 만들어 질 수 있는 갯수는 바로 이전 자릿수에서 j-1, j+1 인 경우일 것이다. 예를 들어 121 이라는 숫자를 만들기 위해서는 12, 10 두 가지 경우 밖에 올 수 없다.
- 그런데 마지막 숫자가 0이나 9인 경우에는 조금 다르다. 0이 만들어지기 위해서는 이전 자릿수의 마지막 숫자로 올 수 있는 숫자가 1밖에 없고, 9가 만들어지기 위해서는 이전 자릿수의 마지막 숫자로 8밖에 올 수 없다. 때문에 0을 만드는 경우의 수는 바로 이전 자릿수의 1을 만드는 갯수인 dp[i-1][j+1] 이 될 것이고, 9를 만드는 경으의 수는 바로 이전 자릿수의 8을 만드는 갯수인 dp[i-1][j-1] 이다.
통과 코드:
#include <iostream>
#include <vector>
#include <numeric>
#define mod 1000000000
using namespace std;
int main (){
int N;
cin >> N;
vector<vector<long long>> dp (N, vector<long long>(10, 1));
for (int i = 1 ; i < N ; i++){
for (int j = 0 ; j < 10 ; j++){
if (j==0) dp[i][j] = (dp[i-1][j+1] % mod); // 0을 만들 수 있는 수는 1 밖에 없으므로 1에 대한 갯수만 더해준다.
else if (j==9) dp[i][j] = (dp[i-1][j-1] % mod); // 9를 만들 수 있는 수는 8 밖에 없으므로 8에 대한 갯수만 더해준다.
else dp[i][j] = (dp[i-1][j-1] % mod + dp[i-1][j+1] % mod); // 0과 9가 아닌 나머지 수들은 모두 j-1, j+1 로 만들 수 있다.
}
}
long long ans = 0;
for(int i = 0 ; i < 9 ; i++){
ans = (ans + dp[N-1][i])%mod;
}
cout << ans;
}
