[알고리즘][Java] 백준(BOJ) 11057 오르막 수_자바

 

DP

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

11057번: 오르막 수

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이 1

<내용>

• n의 범위가 1에서 1000이므로 3중 for문을 돌아도 시간 초과가 발생하지 않을 거라 생각했다.
• n을 Scanner로 입력받는다.
• n = 1 일 때는 0 - 9까지 모두 가능하다.
• n = 2 일 때는 0 뒤에는 0 - 9가, 1 뒤에는 1 - 9가, ..., 8 뒤에는 8 또는 9가, 9 뒤에는 9만 올 수 있다.
• 규칙을 만들면, 해당 숫자 뒤에는 (해당 숫자) - (9)가 올 수 있다.
• 위의 규칙을 이용해서 개수를 세면 된다.
• dp에 초기값이 0인 2차원 배열을 저장한다.
  • dp [n+1][10]의 형태이다.
• 위의 규칙대로 삼중 for문을 돌면서 개수를 저장한다.
• 저장할 때 10007의 나머지를 저장한다.
• 마지막에 출력 전에는 반드시 10007로 나눈 나머지를 출력하는 것을 잊지 않고 한다.

 

 

<코드>

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		
		int[][] dp = new int[n+1][10];
		int mod = 10007;
		for (int i=0; i<10; i++) {
			dp[1][i] = 1;
		}
		
		for (int i=2; i<=n; i++) {
			for (int j=0; j<10; j++) {
				int s = 0;
				for (int k=j; k<10; k++) {
					s += dp[i-1][k];
				}
				dp[i][j] = s%mod;
			}
		}
		
		long res = 0;
		for (int j=0; j<10; j++) {
			res += dp[n][j];
			res %= mod;
		}
		
		System.out.println(res);

	}

}

 

 

 

 

 

 

 

풀이 2

<내용>

• 위의 풀이에서 굳이 int s을 이용해서 dp[i][j]의 값을 알 필요가 없음을 느꼈다.
• 따라서 전체적인 풀이는 같고, int s 대신 직접 dp[i][j]에 합을 더해가서 푼 풀이 방법이다.

 

 

<코드>

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		
		int[][] dp = new int[n+1][10];
		int mod = 10007;
		for (int i=0; i<10; i++) {
			dp[1][i] = 1;
		}
		
		for (int i=2; i<=n; i++) {
			for (int j=0; j<10; j++) {
				for (int k=j; k<10; k++) {
					dp[i][j] += dp[i-1][k];
					dp[i][j] %= mod;
				}
			}
		}
		
		long res = 0;
		for (int j=0; j<10; j++) {
			res += dp[n][j];
			res %= mod;
		}
		
		System.out.println(res);

	}

}

 

 

 

 

 

 

비슷한 문제 : https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수