[BAEKJOON]11057 오르막 수

문제 요약

• 알고리즘 분류: 동적계획법, dp
• 난이도: Silver1
• 문제내용:
  • 수의 자리가 오름차순으로 정렬 되어있는 수를 오르막 수이다.
  • 자리수 N개일때 오르막 수 개수를 구해라.

• 사이트: https://www.acmicpc.net/problem/11057

11057번: 오르막 수

문제풀이

이번 문제는 10의 1000승 만큼 모든 숫자를 구하는 기에는 무리가 있다.

N = int(input())
count = 0
for num in range(0, 10**N):
    flag = 1
    str_num = str(num)
    for i in range(1, len(str_num)):
        if str_num[i] < str_num[i - 1]:
            flag = 0
            break
    count += flag
print(count)

 위 코드 처럼 1 부터 10의 1000승까지에 N만큼 오름 차순으로 구하면 O(10** n  * n) 만큼 복잡도가 나오기 때문에 시간 초과가 나올것이다. 그래서 동적 계획법으로 한다. 동적계획법의 자세한 설명은 여기에 확인 해보면 된다. dp문제는 구현하는 능력보다 아이디어를 요구하기 때문에 점화식을 짜는 방법만 알면 쉽게 풀수 있다. 일단 점화식 구하는 방법은 쉽다.

 

문제 접근 방법

  점화식을 구하는 방법 이전에 자리수마다 나올수 있는 경우의 수를 생각해보면 i 자리의 수는 i - 1 자리수 이하 숫자 밑으로 나올수 있다. 그러면 그 이하의 수 경우의 수를 더하기만 하면된다. 즉 i - 1 이하 숫자 다 더하기만 하면 된다.

다시 처음으로 돌아면 1자리수는 모두다 되기 때문에 1로 선언하고 그 다음 각 자리 수마다  이전 자리수 미만 숫자 다 더 하면된다. 그 다음 N자리까지 다 구하면 N자리 각 숫자를 더해서 출력하면된다.

정리

1. 첫번째 자리수에 0 ~ 9 까지 1로 선언한다.
2.  i 자리에서 i - 1 자리수 이하는 다 더한다.
3. N자리까지 다 구했으면 N자리의 각 숫자의 경우의 수를 다 더해라

Code

Python

N = int(input())
count = 0
for num in range(0, 10**N):
    flag = 1
    str_num = str(num)
    for i in range(1, len(str_num)):
        if str_num[i] < str_num[i - 1]:
            flag = 0
            break
    count += flag
print(count)

 Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	public static void main(String[] args) throws IOException{
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] dp = new int[N + 1][10];
		Arrays.setAll(dp[1], i -> 1);
		for(int i = 2; i <= N; i++) {
			for(int j = 0; j < 10; j++) {
				for(int k = 0; k <= j; k++) {
					dp[i][j] += dp[i - 1][k];
				}
				dp[i][j] %= 10007;
			}			
		}
		System.out.println(Arrays.stream(dp[N]).sum() % 10007);
	}
	
}