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

문제 링크

15990번: 1, 2, 3 더하기 5

---

주의사항

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

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

---

문제 설명

---

접근 방법

다이나믹 프로그램

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

 

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

 

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

 

이 문제에 핵심은

1. 1, 2, 3만 사용할 수 있다.

2. 연속해서 같은 수를 사용할 수 없다.

3. 입력값을 1, 2, 3으로 나타낼 수 있는 경우의 수를 출력한다.

 

배열

 

DP : 메모이제이션 배열

 

 

DP 배열을 이용하여 입력값의 경우의 수를 구하였습니다.

 

이 문제에 대하여 표를 만들어보면 규칙을 찾을 수 있습니다.

 

입력값 1~7까지의 경우를 표로 만들어보았습니다.

	1	2	3	합
1	1	0	0	1
2	0	1	0	1
3	1	1	1	3
4	2	0	1	3
5	1	2	1	4
6	3	3	2	8
7	5	2	2	9

표에 내용을 설명하자면

 

row 값은 1, 2, 3으로 만들어야하는 n의 값입니다.col 값 모든 경우의 수 중 1, 2, 3으로 시작하는 경우의 수를 나눈 것입니다.

 

n = 1일 때경우의 수 = {1}

 

(1,1) = 1

 

(1,2) = 0

 

(1,3) = 0

 

n = 2일 때경우의 수 = {2}

 

(2,1) = 0

 

(2,2) = 1

 

(2,3) = 0

 

n = 3일 때경우의 수 = {1 + 2} , {2 + 1}, {3}

 

(3,1) = 1

 

(3,2) = 1

 

(3,3) = 1

 

n = 4일 때경우의 수 = {1 + 2 + 1}, {1 + 3}, {3 + 1)

 

(4,1) = 2

 

(4,2) = 0

 

(4,3) = 1

 

n = 5일 때경우의 수 = {1 + 3 + 1}, {2 + 1 + 2}, {2 + 3}, {3 + 2}

 

(5,1) = 1

 

(5,2) = 2

 

(5,3) = 1

 

위와 같은 방식으로 표가 진행됩니다.

 

규칙을 찾아보면

 

(n,1) = (n-1, 2) + (n-1 , 3) = 2 + 1 = 3

(n,2) = (n-2, 1) + (n-2, 3) = 2 + 1 = 3

(n,3) = (n-3, 1) + (n-3, 2) = 1 + 1 = 2

 

규칙을 이용하면 경우의 수를 다 만들지 않고 구할 수 있습니다.

 

문제에 해결알고리즘은

1. DP[1][], DP[2][],  DP[3][]을 초기화해줍니다.

2. 위에 규칙대로 DP[][]문을 구성합니다.

3. 입력값을 받으면 DP[N][1] + DP[N][2] + DP[N][3]을 더하여 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• 반복문을 통해 규칙을 적용하여 4~100000에 대한 DP[][]를 구성하였습니다.
• BufferedWriter에 DP[n][0]+DP[n][1]+DP[n][2]을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• init는 DP[1][], DP[2][], DP[3][]을 초기화 하였습니다.

 

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int T,DIV = 1000000009;	//나머지 구할 때 나누어야 할 값
	public static long[][] DP = new long[100001][3];	//메모이제이션
    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
    	T = Integer.parseInt(br.readLine());
    	init();		//초기화 함수 실행
    	
    	for(int i=4;i<100001;i++) {	4~100000까지 경우의 수 구 하기
    		DP[i][0] = (DP[i-1][1] + DP[i-1][2])%DIV;
    		DP[i][1] = (DP[i-2][0] + DP[i-2][2])%DIV;
    		DP[i][2] = (DP[i-3][0] + DP[i-3][1])%DIV;
    	}
    	for(int i=0;i<T;i++) {	//입력값에 해당하는 DP값 찾아서 더하기
    		int n = Integer.parseInt(br.readLine());
    		long result = (DP[n][0] + DP[n][1] + DP[n][2])%DIV;
    		bw.write(result + "\n");	//경우의 수 BufferedWriter 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //DP초기화 함수
    public static void init() {
    	//DP[1][], DP[2][], DP[3][] 초기화
    	DP[1][0] = DP[2][1] = DP[3][0] = DP[3][1] = DP[3][2] = 1;
    	return;
    }
}