[백준 11057] 오르막 수 (자바)

백준 11057번 오르막 수 (자바)

 

 

 

출처

www.acmicpc.net/problem/11057

11057번: 오르막 수

 

 

 

문제

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

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

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

입출력 예

입출력 예 1

 

 

 

접근 방법

이 문제는 일단 공책에 모든 경우의 수를 작성해 보았다.

일정 수가 증가하는 것을 찾을 수는 있었지만, 어떤 것을 기준으로 증가하는지 기준을 찾지 못하였다.

접근 방법을 찾아보니 이차원 배열을 만들어 끝나는 수의 개수를 기준으로 점화식을 만들었다더라..

(이런 생각은 어떻게 하는 거지)

 

위 표는 길이에 따른 끝자리의 모든 경우의 수를 작성한 것이다. 위 표를 개수로 작성한 표가 아래 것이다.

 

검은색 선으로 표시했지만, (-1행의 같은 끝자리+ 같은 행의 -1 끝자리)를 통해 개수가 구해진다는 규칙을 찾을 수 있다.

 

 

점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1]

 

 

 

내 코드

package dynamicprogramming;

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

public class UphillRoadNumber {
	public static void main(String[] args) throws NumberFormatException, IOException {

		//오름차순
		//인접한 수가 같아도 오름차순
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(reader.readLine());
		
		int[][] dp = new int[n+1][10];
		
		//점화식
		//끝자리를 기준으로 2차원 배열
		//n=1 -> 모두 1개
		//dp[i][j] = dp[i-1][j] + dp[i][j-1]
		
		//길이 1은 모두 1개씩
		for (int i=0; i<=9; i++) {
			dp[1][i] = 1;
		}
		
		for (int i=1; i<=n; i++) {
			dp[i][0] = 1;
			for (int j=1; j<=9; j++) {
				dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 10007;
			}
		}
		
		int result = 0;
		for (int i=0; i<=9; i++) {
			result += dp[n][i];
		}
		
		System.out.println(result % 10007);
		
	}//main
}

 

 

 

고려할 점

1. 규칙을 찾아 점화식을 세울 것

2. 직접 써보며 규칙을 찾을 것

3. 끝자리의 개수로 규칙을 찾을 것