🧑🏻‍💻

백준 11057 오르막 수

생성일

2022/07/11 05:16

태그

Python

JAVA

테이블 정의

•

D[i] = 수의 길이가 i 일 때, 오르막 수의 개수

점화식

for (int i = 1; i <= num; i++) {
	for (int j = 0; j <= 9; j++) {
		for (int k = j; k <= 9; k++) {
			arr[i][j] += arr[i-1][k];
		}
	}
}
Java
복사

초기값

for (int i = 0; i <= 9; i++) {
	arr[0][i] = 1;
}
Java
복사

Python

num = int(input())

arr = [[0] * 10 for _ in range(num + 1)]
mod = 10007
int(mod)

for i in range(0, 10):
    arr[0][i] = 1

for i in range(1, num+1):
    for j in range(0, 10):
        for k in range(j, 10):
            arr[i][j] += arr[i-1][k]
            arr[i][j] %= mod
    
print(arr[num][0] % mod)
Java
복사

JAVA

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int num = Integer.parseInt(br.readLine());
		long[][] arr = new long[num+1][10];
	
		for (int i = 0; i <= 9; i++) {
			arr[0][i] = 1;
		}
		
		for (int i = 1; i <= num; i++) {
			for (int j = 0; j <= 9; j++) {
				for (int k = j; k <= 9; k++) {
					arr[i][j] += arr[i-1][k];
					arr[i][j] %= 10007;
				}
			}
		}
		
		System.out.println(arr[num][0] % 10007);
	}	
}
Java
복사

→ Scanner 보다 BufferedReader가 메모리 덜 잡아먹고, 런타임 시간이 더 짧다