[BaekJoon] 백준 11057번 _ 오르막 수 for JAVA

 

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

11057번: 오르막 수

 

 

문제

 

 

---

 

dp문제이다.

 

표를 그려서 확인해보면 감이 온다.

 

 

 

이렇게 그려봤다.

 

열에 있는 0~9까지의 숫자가 각 자리수(행 번호)에 들어갔을 때 나올 수 있는 경우의 수 이다.

 

 

예를 들어 행이 2, 열이 0인 수는

20, 21, 22, 23, 24, 25, 26, 27, 28, 29

 

이렇게 10개가 된다.

 

 

아무튼 저 표를 봤을 때 규칙을 찾을 수 있다.

 

 

노랑 + 노랑 = 핑크

 

노랑 + 노랑 = 핑크

 

라는 규칙을 찾을 수 있었다. 그대로 구현하면 된다.

 

 

 

코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[][] dp = new int[N+1][10];
		for(int i=1; i<=N; i++)
			dp[i][9] = 1;
		
		for(int i=1; i<=N; i++) {
			for(int j=8; j>=0; j--) {
				dp[i][j] = (dp[i][j+1] + dp[i-1][j]) % 10007;
			}
		}
		
		int answer = 0;
		for(int i=0; i<=9; i++)
			answer = (answer+dp[N][i])% 10007;
		
		System.out.println(answer);
	}
}

 

성능

 

 

 

화이팅