[Silver I] 오르막 수 - 11057

문제 링크

성능 요약

메모리: 31256 KB, 시간: 44 ms

분류

다이나믹 프로그래밍

문제 설명

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

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

---

풀이

아이디어

• 직접 종이에 규칙을 그려보았더니, N+1번째 행의 0번째 열이 N번째 행의 합과 같았다.
  직접 만든 점화식은 아래와 같다

사실 점화식 만드는 법을 잘 몰라서 중구난방으로 내 마음대로 만들었는데,,,
암튼 잘 모르겠다.. ㅋㅋ

문제 풀이를 헷갈리지 않게 하기 위해서 0번째 행은 비워두고 1번째 행부터 시작하였다.
mem으로 전체 값을 집어넣을 2차원 리스트를 만들고
반복문을 돌려가며 열 하나씩 업데이트 해주었다.

코드

N = int(input())
mem = [[0]*9 for _ in range(N+2)]
mem[1] = [1] * 10

for i in range(2, N+2):
    tmp = [0]*10
    tmp[0] = sum(mem[i-1])
    for j in range(1, 10):
        tmp[j] = tmp[j-1] - mem[i-1][j-1]
    mem[i] = tmp

print(mem[N+1][0] % 10007)

아래는 풀이 이후 본 다른 코드이다.
내 코드에 비해 메모리를 훨씬 적게 잡아먹는다.

import sys
input = sys.stdin.readline

n = int(input())
dp = [1] * 10

for i in range(n-1):
    for j in range(1, 10):
        dp[j] += dp[j-1]
    
print(sum(dp) % 10007)

---

회고

• 아이디어를 생각하는건 크게 어렵지 않았는데, 이를 재귀로 구현하는데는 어려웠다.
  재귀함수와 분할정복 문제를 풀어보며 익숙해졌다 생각했는데 아직 갈 길이 먼 듯 하다.

• 의외로 반복문으로 풀이했을때는 금방 풀이했다.

• 모든 경우를 다 써볼것,, 임의로 줄여 썼더니 생각이 한정적인데에 박혀있다.