📝 문제 링크
문제 설명
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.예제 입력
| 입력 | 출력 |
|---|---|
| 1 | 9 |
| 2 | 17 |
- DP를 이용한 문제. (100자릿수라서 브루트포스 알고리즘으로는 풀 수 없다.)
d[N][j]: N자리수 중 끝 자리가 j인 숫자.
<Base Case>
- 1자리수에서 끝자리가 1~9인 수의 개수는 각각 1개다. 배열을 1로 초기화 해 줄 것이다.
<Recursive Case>
- N자리수의 끝 자리가 0이면 N-1자리수에서 -1과 1로 끝난 숫자에서 이어질 수 있다. 근데 -1은 존재할 수 없으므로 1 한 가지 경우만 가능.
- N자리수의 끝 자리가 9이면 N-1자리수에서 8과 10으로 끝난 숫자에서 이어질 수 있는데, 10은 존재할 수 없으므로 8의 경우만 가능.
- 0과 9를 제외한 나머지 끝자리 j의 경우는 N-1자리수에서 j-1, j+1의 경우가 모두 가능하다.
코드
#include <iostream>
using namespace std;
int n, d[101][11];
long long ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>n;
//L(1)값에 대해 초기화 해주기
d[1][0]=0;
for(int i=1;i<10;i++) d[1][i]=1;
//계산
for(int i=2;i<=n;i++){
for(int j=0;j<=9;j++){
if(j==0) d[i][j]=d[i-1][j+1]% 1000000000;
else if(j==9) d[i][j]=d[i-1][j-1]% 1000000000;
else d[i][j]=(d[i-1][j-1]+d[i-1][j+1])% 1000000000;
}
}
//결과는
for(int i=0;i<=9;i++) ans+=d[n][i];
cout<<ans%1000000000;
return 0;
}그런데, 왜 중간 연산에도 % 연산을 해줬을까?
- 물론 문제에서 정답이 하도 기니까 %연산을 해서 제출해라~라고 한 건 맞는데, 나는 왜 결과값에만 %연산을 하는게 아니라 중간 계산 과정에서도 %연산을 하는지 궁금했다.
- 물론
d[N]이라는 결과값을 도출하는 과정에서도 long long형의 가용 범위를 넘어간다. 그래서 중간 결과에서도 모듈로 연산이 수행되어야 하는게 맞다. - 중간 연산에 모듈로를 하더라도 결과에 모듈로를 한 것과 같은 영향을 미친다!!!!
간단히 수식으로 풀어서 적어보면
(15+17)%10=2
(15%10+17%10)%10=2
'더해서 나눈 나머지'와 '각자 나눈 나머지의 합에 대해 나눈 나머지'는 같다!!! (말이 쪼꼼 복잡하지만 천천히 읽어보시오)
되돌아보기
d[N][j]배열을 생각해내는 것이 나에겐 어려웠다. 단순히d[N]으로만 받아서 계산하려고 했는데 끝 자리수에 따라서 다음 결과에 영향을 미치기 때문에 단순히 으아~복잡해 하고 생각했다.- 다음 번에 고려할 요소가 또 존재한다면 다차원 배열을 만들어서 값을 저장하는 방법을 떠올리자!
