백준11057 문제 보러가기

문제

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

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

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

입력

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

출력

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

예제 입력

예제 입력 1 : 1
예제 출력 1 : 10
예제 입력 2 : 2
예제 출력 2 : 55
예제 입력 3 : 3
예제 출력 3 : 220

문제 해결

함수로 구현하기

처음에 문제를 읽고 해결하려고 할 때, '어떤 방식으로 푸는 것이 좋을까?'란 생각을 먼저 해봤다.
하나의 방식은 점화식으로 푸는 것이고, 다른 하나의 방식은 while문을 통해 직접 구현을 하는 방식이었다.
다이나믹 프로그래밍(이하 DP)은 점화식을 찾아 풀어야하지만, 나는 두 번째 방식을 택했다. (사실 'DP를 푸는 방식 = 점화식' 이라는 사실을 나중에 알았다.)

나는 먼저 check()라는 함수를 만들어서 문제에서 설명하는 오르막수인지 체크를 하고, return 1을 할 때마다 카운트하는 방식을 생각했다.

그러면 제일 중요한 것은 함수 check이다.
오르막수는 첫 번째 자리 수 부터 마지막 자리 수까지 숫자가 늘어나기만 하면 된다. 중간에 같은 수도 가능하다.
예를 들어, 1234 또는 1355, 11119도 된다는 말이다. 줄어들지만 않으면 된다.
3453, 22232 등 앞의 자리 수보다 작으면 안된다.

문자열로 변환해서 해결할 생각도 해봤지만, 나는 10씩 나누는 방식을 생각했다. 10씩 나누어서 나머지를 확인하면 숫자의 마지막 자리를 확인할 수 있다.

1234 % 10 = 123...4
123 % 10 = 12...3
12 % 10 = 1...2
1 % 10 = 0...1

위와 같이 확인 할 수 있다.
저렇게 되면 첫 번째 자리수부터 확인하는 것이 아니라, 마지막 자리 수 부터 확인할 수 있는데 오르막수의 정의를 살짝 바꿔서 생각하면 된다.
마지막 자리 수 부터 첫 번째 자리 수까지 수가 감소하면 된다.
예시는 앞전에 오르막수 예시 들었던 것과 같다.

그러면 일단 check(num)에서 num은 나눠지는 수를 넣을 것이다. n1이라는 변수를 무한대로 선언한다.
그리고 10으로 나눠서 나머지와 n1의 크기를 비교해서 나머지가 크면, while문을 종료하고 그렇지 않으면 num을 num을 10으로 나눈 몫으로 다시 선언한다. 코드로 작성하면 다음과 같다.

def check(number) :
    n1 = float("inf") # n1 무한대로 선언, 한 자리수가 나왔을 때, 어떤 수가 나오든 무한대보다 클 일은 없기 때문에
    while(1) :
        if number % 10 == 0 :
            return 0 # 자리 수가 0이 나오면 무조건, 오르막 수 아님
        else :
            if number % 10 > n1 : # 지금 자리수 > 이전 자리 수
                return 0
            else:
                if number // 10 == 0 : # 몫이 0이면 첫 번째 자리 수까지 도달
                    return 1
                else : 
                    n1 = number % 10 # 아직 숫자가 남음, n1을 지금 자리수로 다시 선언
                    number = number // 10 # 예시 : 1234 -> 123

그래서 return 값이 1이면, 선언한 변수 cnt에 1씩 추가하고, return 값이 0이면 그냥 pass 하도록 해서 전체 코드는 다음과 같이 짰다.

def check(number) :
    n1 = float("inf")
    while(1) :
        if number % 10 == 0 :
            return 0
        else :
            if number % 10 > n1 :
                return 0
            else:
                if number // 10 == 0 :
                    return 1
                else : 
                    n1 = number % 10
                    number = number // 10 
                    
num = int(input())
cnt = 0
for i in range(10**num) :
    if check(i) == 1 :
        cnt += 1
    else : 
        pass
    
print(cnt%10007+1) # +1 은 '0'을 카운트한 것이다.

그런데 아쉽게도, 백준 채점 기준으로는 시간 초과가 떴다.

그러면 이렇게 푸는 것이 아니라, 다른 방법으로 푼다는 것인데 이 때 나는 검색하고 주위 사람들에게 물어본 결과 DP는 이렇게 푸는 것이 아니라는 것을 알았다.

DP는 점화식을 토대로 풀어서, 더욱 간단하게 해결하는 방식이라는 것을 알게 되었다.

점화식 찾기

참고 블로그
https://animoto1.tistory.com/entry/%EB%B0%B1%EC%A4%80-11057-%EC%98%A4%EB%A5%B4%EB%A7%89-%EC%88%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python
(위 블로그를 참고했다.)

점화식을 찾기 위해서 규칙을 찾아야한다.
일단, 자리 수를 입력하면, 그에 맞는 개수가 나오는 형식이어야 한다.
위를 따르면, 1을 입력하면 10이, 2를 입력하면 55가 출력된다.

일단 먼저, 자리 수에 따른 오르막수를 찾아보자.

자리 수 : 1
오르막수 : 0 1 2 3 4 5 6 7 8 9
자리수 : 2
오르막수 : 11 12 13 14 15 16 17 18 19 / 22 23 24 25 26 27 28 29 ... / 99

이렇게 했을 때, 사실 나는 바로 규칙을 못 찾았다.
하지만 블로그를 참고해보니 일의 자리 수를 기준으로 써서 점화식을 찾았다.

자리 수 : 1
오르막 수 : 0 1 2 3 4 5 6 7 8 9
자리 수 : 2
오르막 수 : 00 / 01 11 / 02 12 22 / 03 13 23 33 / 04 14 24 34 44 / ... / 09 19 29 ... 99
자리 수 : 3
오르막 수 : 000 / 001 011 111 / 002 012 022 112 122 222 / 003 013 023 033 113 123 133 223 233 333 / ... / 009 019 029 039 049 059 069 079 089 099 119 129 ... 999

규칙이 보이는가? 위를 표로 나타냈을 때, 다음과 같이 표현할 수 있다.

자리수 / 일의 자리 수	0	1	2	3	4	5	6	7	8	9
1	0(1)	1(1)	2(1)	3(1)	4(1)	5(1)	6(1)	7(1)	8(1)	9(1)
2	00 (1)	01 11 (2)	02 12 22 (3)	03 13 23 33 (4)	...(5)	...(6)	...(7)	...(8)	...(9)	09 19 29 39 49 59 69 79 89 99 (10)
3	000 (1)	001 011 111 (3)	002 012 022 112 122 222 (6)	...(10)	...(15)	...(21)	...(28)	...(36)	...(45)	...(55)

[i][j]의 값은 [i-1][j] + [i][j-1] 값과 같은 것이다.
그래서 아래와 같이 간단하게 표현할 수 있다.

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