쉬운 계단 수(10844)
이 문제를 풀때의 문제점
1. 문제에서 주는 힌트를 충분히 이해하지 않고 넘어갔다.
나는 이문제를 아래와 같이 접근하였다.
- 이 문제에서는 입력으로 이 주어지는데 은 계단수의 자리수를 뜻하며 이것은 보다 작은 자연수이다.
- 예제에 두 자리까지 예시가 나왔으니 어떻게 이러한 출력이 나왔는지를 이해해 보자.
-
조건에서 에서 시작하는 수는 없다고 했기 때문에 한 자리의 계단수는 1 ~ 9까지 개이다. 두 자리의 계단수 경우 첫번째 자리가 일경우 과 가 가능하고, 일경우 과 가 가능하며 일경우 만가능하다.
1 0, 2 2 1, 3 3 2, 4 4 3, 5 5 4, 6 6 5, 7 7 6, 8 8 7, 9 9 8
-
이러한 규칙으로 두자리의 계단수는 가지가 된다. 첫번째 자리가 일때의 경우만 확인해보면 다음과 같이 세 가지 계단수가 나온다.
1 - 0 - 1 - 2 - 1 - 3
-
이정도 해보니 번째 수는 번째 수 + 1 혹은 번째 수 - 1 이라는 반복되는 규칙을 찾을 수 있었다.
long long solve(int length, int num){ if(num > 9 || num < 0){ return 0; } if(length == 1){ return d[1][num]; // 1로 설정할경우 오답이다. 이유는 모르겠다.ㅍ } return solve(length+1, num - 1) + solve(length+1, num + 1); }
하지만 여기까지 접근한 내용은 이미 문제에 언급되어있다. 계단수에 대한 설명이 그것이다. 즉 문제만 잘 이해해도 이러한 시간낭비를 줄일 수 있다.
2. 시간복잡도를 예측하지 못했다.
이 문제에서는 은 최대 이고, 자리가 증가할때마다 약 2배씩 만들수 있는 계단수의 경우의 수가 증가한다. 따라서 연산의 횟수가 약 번 정도이고, 브루트 포스로 풀 수 없는 문제이다. 또한 이 판단에는 매번 자리가 올라갈때마다 N-1과 N+1 연산이 반복된다는 것을 토대로한 추측이다. 그래서 시간복잡도를 예측하는것 만으로도 ‘브루트포스로 풀 수 없고, 반복되는 연산이 있으므로 다이나믹프로그래밍으로 풀어보자.’ 라는 합리적인 접근이 가능해진다. 물론 이러한 접근이 매번 맞을 수는 없지만 근거없는 접근보다는 이후 또 다른 문제를 풀때에도 도움이 될것이다.
3. 반복되는 연산을 증명하지 않고 넘어갔다.
다이나믹 프로그래밍을 사용하기 전에는 분할한 문제들이 반복되며, 매번 같은 값을 반환한다는것을 증명해야한다. 이 문제에서는 반복되는 문제가 쉽기 때문에 쉽게 추론할 수 있었지만, 어떤 문제가 어떻게 반복되는지 스스로 확실하게 정의 내리고 문제를 푸는 습관을 들이는 것이 좋을것 같다.
- 첫번째 자리가 일떄 세 자리 계단수는 항상 다음과 같은 세 가지 계단수가 만들어진다.
1 - 0 - 1
- 2 - 1
- 3
- 이것을 배열에 저장하면
d[1][3]
이 된다. (배열에 어떤 방법으로 어떤 값을 저장해야 하는지까지 확실히 정의할 수 있게됨)
최종코드
#include <stdio.h>
long long MOD = 1000000000;
long long d[101][10];
long long solve(int length, int num){
if (num > 9 || num < 0){
return 0;
}
if(length == 1){
return d[1][num]; // 1로 설정할경우 오답이다. 이유는 모르겠다.
}
if(d[length][num] == 0){
d[length][num] = solve(length - 1, num - 1) + solve(length - 1, num + 1);
d[length][num] %= MOD;
}
return d[length][num];
}
int main(){
int n;
long long result = 0;
scanf("%d", &n);
for (int i = 1; i <= 9; i++) d[1][i] = 1;
for (int i = 0; i <= 9; i++){
result += solve(n, i);
}
printf("%lld", result % MOD);
return 0;
}