쉬운 계단 수(10844)

이 문제를 풀때의 문제점


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

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

  • 이 문제에서는 입력으로 NN이 주어지는데 NN은 계단수의 자리수를 뜻하며 이것은 100100보다 작은 자연수이다.
  • 예제에 두 자리까지 예시가 나왔으니 어떻게 이러한 출력이 나왔는지를 이해해 보자.
  • 조건에서 00에서 시작하는 수는 없다고 했기 때문에 한 자리의 계단수는 1 ~ 9까지 99개이다. 두 자리의 계단수 경우 첫번째 자리가 11일경우 0022가 가능하고, 88일경우 7799가 가능하며 99일경우 88만가능하다.

    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
  • 이러한 규칙으로 두자리의 계단수는 1717가지가 된다. 첫번째 자리가 11일때의 경우만 확인해보면 다음과 같이 세 가지 계단수가 나온다.

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

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


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

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


  • 첫번째 자리가 11일떄 세 자리 계단수는 항상 다음과 같은 세 가지 계단수가 만들어진다.
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;
}