챕터3-8. DP | 문제 풀이2 - (2) 백준 No.10844 : 쉬운 계단 수

쉬운 계단 수 문제

- https://www.acmicpc.net/problem/10844

문제요약

정수 N이 주어지는데 인접한 자리의 수 차이가 모두 1인 수를 '계단 수' 라고 칭한다. ex) 45656
길이가 N인 계단 수의 개수를 구하고 1000000000로 나눈 나머지를 출력하라.

해결 방법

1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N][L] = "L로 끝나는 길이가 N인 '계단 수' 의 개수"

- 이전 문제에서는 0 또는 1만 왔는데, 여기는 한 자리에 0~9가 올 수 있기 때문에 1차원으로 문제를 풀 수 없다.
   따라서 2차원 배열을 활용하게 된다.

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 정수 N이 주어지고, 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다.

 

case 1) N번째 자리에 L이 올 때 N-1번째 자리에 L-1이 오는 경우

 

case 2) N번째 자리에 L이 올 때 N-1번째 자리에 L+1이 오는 경우

 

따라서, 점화식은 D[N][L] = D[N-1][L-1] + D[N-1][L+1] (1<=L<=8)이고, 

                               L = 0 인 경우, D[N][0] = D[N-1][1] 이고,

                               L = 9 인 경우, D[N][9] = D[N-1][8] 이다.

 

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

 

4. 코드구현

- 1000000000으로 나눈 나머지를 구하라는 유형의 문제이기 때문에 d 배열에 나머지를 저장해줘야 한다는 것을 주의하자.
   또한, 마지막 출력할 전 d[n][0] ~ d[n][9] 를 모두 더하는데 이 더한 값 또한 1000000000 으로 나눠줘야 한다는 것을 명심하자.

<Top-down 방식>

2차원 배열을 사용하므로 Bottom-up 방식으로 쉽게 구하자.

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>

using namespace std;

int d[101][10];

int main()
{
    int n;
    cin >> n;

    // n이 1일 때 결과가 9이므로 해주는 초기화
    for (int i = 1; i <= 9; i++)
        d[1][i] = 1;

    // d 계산하기
    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];

            else if (j == 9)
                d[i][j] = d[i-1][j-1];

            else
                d[i][j] = d[i-1][j-1] + d[i-1][j+1];

            d[i][j] %= 1000000000;
        }            
    }

    // 구해진 d 합하여 출력하기
    long long sum = 0;

    for(int i = 0; i <= 9; i++)
        sum += d[n][i];
        
    cout << sum % 1000000000 << endl;
}

(2) 시간복잡도
= for 문의 반복 횟수 

= 9 * N = O(N)