[백준] code.plus(다이나믹 프로그램 part 2,JAVA)11057번, 오르막 수

문제 링크

11057번: 오르막 수

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

다이나믹 프로그램

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

 

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 오르막 수를 만들 수 있는 개수를 출력해야한다.

2. 1~9까지 숫자는 중복되어 사용할 수 있습니다.

3. 0은 시작 값으로 사용할 수 있습니다.

4. 결과를 출력할 때 10007로 나눈 나머지를 결과로 출력한다.

 

배열

 

DP : 메모이제이션 배열

 

DP[][10] 배열을 이용하여 오름차 수에 대한 경우의 수를 구하였습니다.

 

DP[i][j]의 값은 길이가 i인 오르막 수를 구성할 때 0~j의 숫자 범위에서의 오르막 수의 경우의 수를 저장합니다.

 

예제 입력3의 DP표를 표현하면

	0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	10	15	21	28	36	45	55

 

표를 통해 규칙을 발견할 수 있습니다.

DP[i][j] = DP[i][j-1] + DP[i-1][j]

 

위 규칙이 나오는 이유는

DP[3][2]일 때 경우의 수는

최대값이 3이 아닌 오르막 수의 경우의 수 + 길이가 2이고 최대값이 3인 오르막 수의 경우의 수

= DP[3][2] + DP[2][2]로 표현할 수 있습니다.

 

표에 규칙을 적용하면

 

DP[2][5] = DP[2][4] + DP[1][5] = 5 + 1 = 6

DP[3][4] = DP[3][3] + DP[2][3] = 10 + 5 = 15

 

모든 경우의 수를 나타내는 값은 DP[N][0~9]로

예제입력 3에서의 답은 DP[3][0~9]입니다.

모든 경우의 수 : DP[3][0] + DP[3][1] + ... + DP[3][9] = 1 + 3 + .... + 55 = 220

 

모든 경우의 수 220을 결과로 출력합니다.

 

문제에 해결알고리즘은

1. DP[1][0~9]의 값을 1로 초기화해줍니다.

2. 규칙을 적용하여 DP[][]를 구성합니다.

3. DP[N][0~9]의 합을 10007으로 나눈 나머지를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• DP[1][0~9]의 값을 1로 초기화해주었습니다.
• 규칙을 적용하여 DP를 구성하는 cal함수를 만들었습니다.
• BufferedWriter에 DP[n][0~9] 합을 10007로 나눈 나머지 값을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• cal은 반복문을 통해 위에 설명한 규칙을 적용시켜주었습니다.

결과 코드

import java.io.*;
import java.util.Arrays;
public class Main{
	static int[][] DP;	//메모이제이션 배열
	static int[] count;	//각 길이의 모든 경우의 수 저장하는 배열
	static int DIV = 10007;		//나머지를 구하기 위해 나누는 값
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 배열 초기화----------
    	int N = Integer.parseInt(br.readLine());
    	DP = new int[N+1][10];
    	count = new int[N+1];
    	count[1] = 10;
    	Arrays.fill(DP[1], 1);
    	cal(N);		//DP구성하는 함수 실행
    	bw.write(count[N] + "\n");		//모든 경우의 수 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();  	
    }
    //규칙을 적용하여 반복문으로 DP 구성하는 함수
    static void cal(int N) {
    	for(int i=2;i<=N;i++) {
    		int sum = 1;
    		DP[i][0] = 1;
    		for(int j=1;j<10;j++) {
    			DP[i][j] = (DP[i][j-1] + DP[i-1][j])%DIV;	//규칙 1
    			sum = sum + DP[i][j];			//경우의 수 더하기
    		}
    		count[i] = sum % DIV;		//해당 길이 모든 경우의 수 저장
    	}
    	return;
    }
}