이 문제를 풀때의 문제점

1. 문제에서 주는 힌트를 충분히 이해하지 않고 넘어갔다.

나는 이문제를 아래와 같이 접근하였다.

• 이 문제에서는 입력으로 $N$이 주어지는데 $N$은 계단수의 자리수를 뜻하며 이것은 $100$보다 작은 자연수이다.
• 예제에 두 자리까지 예시가 나왔으니 어떻게 이러한 출력이 나왔는지를 이해해 보자.

• 조건에서 $0$에서 시작하는 수는 없다고 했기 때문에 한 자리의 계단수는 1 ~ 9까지 $9$개이다. 두 자리의 계단수 경우 첫번째 자리가 $1$일경우 $0$과 $2$가 가능하고, $8$일경우 $7$과 $9$가 가능하며 $9$일경우 $8$만가능하다.

  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

• 이러한 규칙으로 두자리의 계단수는 $17$가지가 된다. 첫번째 자리가 $1$일때의 경우만 확인해보면 다음과 같이 세 가지 계단수가 나온다.

  1 - 0 - 1
    - 2 - 1
        - 3

• 이정도 해보니 $N$번째 수는 $N-1$번째 수 + 1 혹은 $N-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. 시간복잡도를 예측하지 못했다.

이 문제에서는 $N$은 최대 $100$이고, 자리가 증가할때마다 약 2배씩 만들수 있는 계단수의 경우의 수가 증가한다. 따라서 연산의 횟수가 약 $2^{100}$ 번 정도이고, 브루트 포스로 풀 수 없는 문제이다. 또한 이 판단에는 매번 자리가 올라갈때마다 N-1과 N+1 연산이 반복된다는 것을 토대로한 추측이다. 그래서 시간복잡도를 예측하는것 만으로도 ‘브루트포스로 풀 수 없고, 반복되는 연산이 있으므로 다이나믹프로그래밍으로 풀어보자.’ 라는 합리적인 접근이 가능해진다. 물론 이러한 접근이 매번 맞을 수는 없지만 근거없는 접근보다는 이후 또 다른 문제를 풀때에도 도움이 될것이다.

3. 반복되는 연산을 증명하지 않고 넘어갔다.

다이나믹 프로그래밍을 사용하기 전에는 분할한 문제들이 반복되며, 매번 같은 값을 반환한다는것을 증명해야한다. 이 문제에서는 반복되는 문제가 쉽기 때문에 쉽게 추론할 수 있었지만, 어떤 문제가 어떻게 반복되는지 스스로 확실하게 정의 내리고 문제를 푸는 습관을 들이는 것이 좋을것 같다.

• 첫번째 자리가 $1$일떄 세 자리 계단수는 항상 다음과 같은 세 가지 계단수가 만들어진다.

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;
}