[백준] 11057 오르막 수 / python

문제

https://www.acmicpc.net/problem/11057

 

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

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

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

입력

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

출력

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

 

 

---

코드

처음에 두번째 시간 초과 코드를 거의 1분만에 짜고 냈다가 시간초과가 떴다.

이렇게 쉬울 리가 없자나.....ㅜ

곧 시간복잡도, 공간복잡도를 고려해면서 풀 수 있는 실력이 되겠지..?

정답 코드 ( DP 사용)

import sys
input = sys.stdin.readline

n = int(input())

dp = [[0] * 10 for _ in range(n+1)]

for j in range(10):
    dp[1][j] = 1

for i in range(2, n+1):
    for j in range(10):
        dp[i][j] = sum(dp[i-1][k] for k in range(j+1))

result = sum(dp[n][j] for j in range(10))
print(result % 10007)

 

dp[i][j] 테이블을 사용한다. i는 자릿수, j는 자릿수의 끝값을 나타낸다.

즉 dp[2][3] 이라면 (03, 13, 23)이 해당되기 때문에 3이된다.

생각해보면 dp[2][3]은 dp[1][3보다 같거나 작은 모든 수] 값들 뒤에 3만 붙인 것과 같다.

 

그렇다면, 점화식은 아래와 같다.

dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j] 

점화식을 이용해 테이블을 채우고, 마지막 자릿수에서 가능한 모든 값을 더하여 결과를 출력하면 result값이 나오고,

최종적으로 result값을 10007로 나눈 나머지를 출력하면 정답이 된다.

 

누적합을 사용하면 합을 계산하는 시간이 O(1)이 되고, dp 배열을 계산하는 시간은 O(n*10)이다.

따라서 전체 시간 복잡도는 O(n*10) 즉 O(n)이 된다.

 

시간 초과 코드 (단순 비교 방식)

import sys
input = sys.stdin.readline

n = int(input())

def func(n):
    n = str(n)
    for i in range(1, len(n)):
        if n[i-1] > n[i]:
            return False
    return True

if n == 1:
    print(10)
else:
    cnt = 0
    for i in range(10**n):
        if func(i):
            cnt += 1
    print(cnt)

 

이 코드는 그냥 오름차순 조건을 만족하는 지 모든 숫자를 체크하는 방식이다.

위 코드에서 func(i)의 시간 복잡도는 O(n의 자릿수)이다.

결국 i가 0부터 10^n -1까지 즉 10^n 번 func(i)를 반복하기 때문에

전체 시간 복잡도는 O(10^n * n)이다.

 

 

 

• 첫 번째 코드는 DP를 사용하여 시간 복잡도를 최적화할 수 있으며, 자릿수가 커지더라도 비교적 효율적으로 증가하는 수의 개수를 계산할 수 있다.
• 두 번째 코드는 단순 비교 방식으로, 자릿수가 커질수록 시간이 급격히 증가하여 시간 초과가 발생할 수 있다.

 

---

오랜만에 DP 문제 푸는 거라, DP 개념정리도 다시 한번 적어두려고 한다.

DP ( Dynamic Programming)

동적 계획법은 문제를 더 작은 부분 문제로 나누어 풀고, 각 부분 문제의 결과를 저장해두고 이를 재사용하는 방법이다.

이미 계산된 결과를 저장하여 반복 계산을 피할 수 있으며, 주어진 문제를 풀기 위한 최적의 해를 찾을 수 있다.

중복 계산을 방지하기 때문에 시간 복잡도가 크게 줄어든다.