[0530] 알고리즘

10844. 쉬운 계단 수

  어제 푼 문제와 같은 다이내믹 프로그래밍 문제.

  자릿수를 N이라고 할 때, N자리의 계단 수는 N-1자리의 각 계단 수의 끝 숫자의 -1, +1된 수를 붙이면 나온다는 아이디어는 대충 떠올랐는데, 이걸 코드로 나타내는데 애먹고 채점할 땐 예상치 못한 무언가에 또 애먹었었다.

 

  과제로 수행했던 다이내믹 프로그래밍 문제는 Top-down방식이었어서 재귀를 써야하나 싶었는데, 도대체 어떻게 재귀를 쓰나에서 시작해서 생각을 거치다 다이내믹은 반복문을 사용하는 Bottom-up이라는 방식이 있었음을 떠올렸다... 어렴풋이 배우고 안 써먹으면 이렇게 얼레벌레 알게 되는 것 같다. 코드는 아래와 같았음.

 

#include <iostream>

int main()
{
    int n;
    long long sum = 0;

    std::cin >> n;

    //배열 생성
    long long** dpArr = new long long* [n];

    for (int i = 0; i < n; i++)
    {
        dpArr[i] = new long long[10];
    }

    //배열 초기화
    dpArr[0][0] = 0;
    for (int i = 1; i < 10; i++)
    {
        dpArr[0][i] = 1;
        sum++;
    }

    //N이 2 이상일 때의 계단 수 구하기
    for (int i = 1; i <= n - 1; i++)
    {
        sum = 0;
        dpArr[i][0] = dpArr[i - 1][1];
        dpArr[i][9] = dpArr[i - 1][8];

        sum += dpArr[i][0];
        sum += dpArr[i][9];

        for (int j = 1; j < 9; j++)
        {
            dpArr[i][j] = (dpArr[i - 1][j - 1] + dpArr[i - 1][j + 1]) % 1000000000;
            sum += dpArr[i][j];
        }
    }

    std::cout << sum % 1000000000 << '\n';

    return 0;
}

 

---

  처음에 짜놓고 실패했을 때는 자료형을 int로 잡은 나머지 int의 범위를 넘어버려서 문제가 생겼었다. 그래서 더 큰 long long 형을 사용한 것 까진 그렇다 쳤는데... 그 이후로도 계속 실패가 떠서 ??? 하고 있던 찰나, 타 코드를 살펴 저 '%1000000000'를 안 넣어서 실패가 떴음을 알 수 있었다(!).

 

  알아보니 대충 처음 문제와 비슷한 이유가 원인이었다. 정수의 오버플로우 때문에 중간에도 계속 % 처리를 해주는 거라고... 문제 답을 저렇게 나눈 나머지로 출력하라는 것부터 특이하다 싶었는데 그런 이유가 숨어있는 줄 몰랐다. 자료형도 잘 알아두기.