[C++ / 11057] 오르막 수

문제

11057번: 오르막 수

---

문제 설명

오르막 수는 수가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

- 가능: 2234, 3678, 11119

- 불가능: 2232, 3676, 91111

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하라.

0으로 시작가능.

---

풀이 방식

다음 이미지대로 하면 된다. 이게 DP의 방식 인지는 모르겠는데.. 이전의 값을 가지고 와서 현재의 값을 만들어 낸다.

다음 그림의 설명을 하기 위해 n=2일때를 예시로 들겠다.

n=2의 경우를 Brute Force 처럼 구해보면 다음과 같다.

• 9 - 99
• 8 - 88, 89
• 7 - 77, 78, 79
• 6 - 66, 67, 68, 69
• 5 - 55, 56, 57, 58, 59
• 4 - 44, 45, 46, 47, 48, 49
• 3 - 33, 34, 35, 36, 37, 38, 39
• 2 - 22, 23, 24, 25, 26, 27, 28, 29
• 1 - 11, 12, 13, 14, 15, 16, 17, 18, 19
• 0 - 00, 01, 02, 03, 04, 05, 06, 07, 08, 09

이렇게 총 55개가 존재한다. 이를 저 배열에 넣어 둔 것이다.

그렇게 n 자리수 마다 구하면 되는데 이를 점화식으로 만들어 보면 다음과 같다.

DP[i][j] = DP[i][j-1] + DP[i-1][j]

이를 이용하여 코딩하면 된다.

---

솔루션

#include <iostream>

using namespace std;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  int save = 0, result = 0;

  int arr[1001][1001];

  cin >> n;

  if (n == 1)
  {
    cout << 10;
    return 0;
  }

  for (int i = 0; i < 10; i++)
    arr[0][i] = 1;

  for (int i = 0; i < n - 1; i++)
  {
    for (int j = 0; j < 10; j++)
    {
      arr[i + 1][j] = (save + arr[i][j]) % 10007;
      save = arr[i + 1][j];
    }
    save = 0;
  }

  for (int i = 0; i < 10; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      result += arr[n - 2][j];
      result %= 10007;
    }
  }

  cout << result << endl;
  return 0;
}

---

여담

DP에 대해서 나름 요령이 생긴 것 같다! 이게 제대로 풀고 있는 건지는 잘 모르겠지만.. 아직 알고리즘을 구성하는데 있어서는 어색하다.

 

위에 짠 코드가 최적.. 은 아니다 문제가 있긴 하지만.. 또 이걸 최적화 할 시간에 다른 문제를 풀어보는게 알고리즘 풀이의 매력이 아닐까 싶기도 하다..ㅋㅋ

 

c++이 아직 익숙하지 않아서 그냥 배열로 충분한 것을 vector로 자꾸 구현하려고 하고 타입에러를 낼까봐 이것저것 찾아보고 있다..ㅎㅎ 화이팅~!!