문제

BOJ 11057: 오르막 수 https://www.acmicpc.net/problem/11057

풀이

조건

• 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다.
  • 이때, 인접한 수가 같아도 오름차순으로 친다.
• 수는 0으로 시작할 수 있다.
• 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구한다.

풀이 순서

• DP를 사용한다.

• 메모이제이션할 배열은 2차원 배열로 생성한다.

  • 배열의 행은 오르막 수의 길이, 열은 오르막 수의 마지막 수의 값이다.

    길이가 3인 오르막 수의 총 개수를 구하는 경우

    	0	1	2	3	4	5	6	7	8	9	total 오르막 수
    N=1	1	1	1	1	1	1	1	1	1	1	10
    N=2	1	2	3	4	5	6	7	8	9	10	55
    N=3	1	3	6	10	15	21	28	36	45	55	220

  • 길이가 1 일 땐 모두 자기 자신이 오르막 수이기 때문에 1이 기록된다.

  • 길이가 i인 오르막 수의 끝 자리가 j일 때의 수는 길이가 i - 1인 0 ~ j 까지의 오르막 수의 합과 같다.

코드

Java

import java.util.*;
import java.io.*;

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());
		
		// 길이가 1 -> 모두 자기 자신이라서 오르막 수는 1개씩 있음
		long[][] dp = new long[N + 1][10];
		for (int i = 0; i < 10; i++) {
			dp[1][i] = 1;
		}
		
		// 길이가 i일 때 오르막 수 구하기
		for (int i = 2; i <= N; i++) {
			// 끝 자리가 j일 때 오르막 수 구하기
			for (int j = 0; j < 10; j++) {
				// 이전 길이(i-1)일 때 끝 자리가 j보다 작은 모든 수들을 더함
				for (int k = 0; k <= j; k++) {
					dp[i][j] += dp[i-1][k];
				}
				dp[i][j] %= 10007;
			}
		}
			
		long answer = 0;
		for(int i=0; i<10; i++) {
			answer += dp[N][i];
		}
		
		System.out.println(answer % 10007);
	}

}

정리

• 규칙을 보고 식을 일반화해서 해결했다.