10844

백준 10844번

Link: 10844번: 쉬운 계단 수

---

문제 설명

어제는 피곤함에 빈둥거리다 아무것도 못올렸다.

이 문제는 어제부터 고민하다 방법을 찾았고, 그 방법을 어떻게 구현할지 많은 시행착오를 거친 끝에 결국 풀었다.

사실 맨 마지막에 내 생각이 확실한데 답이 자꾸 틀려서 다른사람 답을 찾아보긴 했지만, 그 답이 내가 생각한 그대로여서 여태껏 답 찾아본 문제들중 가장 치열하게 고민한 문제인 것 같다는 생각을 했다.

그만큼 이번에는 답찾아서 풀었음에도 쪽팔리다는 생각이 들지 않았고.

각설하고, 푸는 방법에 대해 설명해보자면 이 문제에서 각 자릿수가 몇자리수이냐는 아무 상관이 없다.

가장 중요한 것은 1의자리 숫자가 무엇인지.

N이 1일때, 2일때, 3일때의 경우들을 직접 구해보니 1의자리 숫자에 따라 다음 수가 영향을 받는다는 것을 알 수 있었다.

자꾸 보다보니 N일때의 답 = (N-1일때의 답 * 2) - (N-1일때의 계단수 중 첫자리 숫자가 1인 것의 갯수) 라는 규칙을 찾은것같은데, 맞는지는 모르겠다.

어떻게 구현할지 한참 고민하다 저 규칙대로 풀어보기 위해 우선 큐에 넣고 갱신해가면서 모든 경우를 다 돌려봤다.

한 5분은 지나야 전체 답을 구할 수 있더라.

이런 과정을 거치면서 이 문제를 어떻게하면 이전 N에서 얻은 답을 사용할수 있을지에 대해 중점적으로 고민해보았고, 결국 1의자리 숫자만이 영향을 미친다는 점을 찾기에 이르렀다.

이 문제를 풀며 가장 고무적이었다고 생각했던 부분은 DP의 특성을 어떻게든 적용하기 위해 노력했다는 점.

앞에서 구한 답을 어떻게 써먹을수 있는지 그 어느때보다 치열하게 고민한 것 같다.

이 문제를 풀어낸 것이 앞으로 DP문제를 푸는데 있어 전환점이 되길!!

---

정답 코드

//
// Created by Keith_Lee on 08/01/2019.
//

#include <iostream>
#include <strings.h>

using namespace std;

int main(){
    int N;

    cin >> N;

    unsigned long long DP[101][11];
    bzero(DP, sizeof(DP));

    for(int i=1; i<10; i++){
        DP[1][i] = 1;
    }

    for(int i=2; i<=N; i++) {
        DP[i][0] = DP[i-1][1];
        for(int j=1; j<10; j++){
            DP[i][j] = (DP[i-1][j-1] + DP[i-1][j+1]) % 1000000000;
        }
    }

    unsigned long long sum = 0;
    for(int i=0; i<10; i++){
        sum += DP[N][i];
    }
    cout << (sum % 1000000000) << '\n';

    return 0;
}

---