[백준] code.plus(다이나믹 프로그램 part 2,JAVA)15988번, 1, 2, 3 더하기 3

문제 링크

15988번: 1, 2, 3 더하기 3

---

주의사항

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

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

---

문제 설명

---

접근 방법

다이나믹 프로그램

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

 

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

 

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

 

이 문제에 핵심은

1. 1, 2, 3의 합으로 n이 나오는 경우의 수를 출력한다.

2. 1, 2, 3은 중복되어 사용이 가능하다.

3. 결과를 출력할 때 1,000,000,009을 나눈 나머지를 출력한다.

 

배열

 

DP : 메모이제이션 배열

 

DP 배열을 이용하여 1, 2, 3을 더해서 N이 되는 경우의 수를 구하였습니다.

 

DP[i]는 1, 2, 3을 더해서 i가 나오는 경우의 수를 저장하였습니다.

 

이 문제에서 만약 입력값이 N = 4일 때 경우의 수는

 

4 = 3(1, 2, 3의 합으로 3이 나오는 경우의 수) + 1

4 = 2(1, 2, 3의 합으로 3이 나오는 경우의 수) + 2

4 = 1(1, 2, 3의 합으로 3이 나오는 경우의 수) + 3

 

위 경우의 수를 모두 더하는 것을 DP의 형태로 나타내면

DP[4] = DP[3] + DP[2] + DP[1]

 

DP[i] = DP[i-1] + DP[i-2] + DP[i-3]라는 식을 얻을 수 있습니다.

 

N = 4일 때의 DP[]배열을 표로 표현하면

DP	1	2	3	4
	1	2	4	7

 

위에 표에서 값을 살펴보면

 

N = 1일 때 {1} = 1N = 2일 때 {1 + 1, 2} = 2N = 3일 때 {1 + 1 + 1, 1 + 2, 2 + 1, 3} = 4

 

DP[4] = DP[3] + DP[2] + DP[1] = 4 + 2 + 1 = 7

 

위 경우를 반복하여 DP를 구성한 뒤 입력값에 따른 DP[n]을 결과로 출력합니다.

 

문제에 해결알고리즘은

1. 입력값을 받아서 규칙을 적용해서 DP[]를 구성합니다.

2. DP[n]을 1,000,000,009나눈 나머지를 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 통해 n을 띄어쓰기 기준 분리하였습니다.
• DP[1~3]의 값을 초기화해주는 init 함수를 만들었습니다.
• 규칙을 적용하여 DP를 구성하는 cal함수를 만들었습니다.
• BufferedWriter에 DP[n]값을 1,000,000,009나눈 나머지 값을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• cal은 반복문을 통해 위에 설명한 규칙을 적용시켜주었습니다.
• init는 DP[1~3]의 값을 초기화해주었습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static long[] DP = new long[1000001];	//메모이제이션 배열
	static int DIV = 1000000009;		//나머지 구하기 위해 나누는 값
    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());
    	init();	//DP[1], DP[2], DP[3] 초기화하는 함수 실행
    	cal();	//규칙 적용하여 DP구성하는 함수 실행
        //입력값에 따라 DP값 BufferedWriter 저장
    	for(int i=0;i<n;i++) {
    		int num = Integer.parseInt(br.readLine());
    		bw.write(DP[num] + "\n");
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //DP[1],DP[2],DP[3] 초기화하는 함수
    static void init() {
    	DP[1] = 1;
    	DP[2] = 2;
    	DP[3] = 4;
    	return;
    }
    //규칙을 적용하여 4~1000001의 DP값 구성하는 함수
    static void cal() {
    	for(int i=4;i<1000001;i++) 
    		DP[i] = (DP[i-1] + DP[i-2] + DP[i-3])%DIV;	//규칙 적용
    	return;
    }
}