[백준] code.plus(다이나믹 프로그래밍,JAVA)15989번, 1, 2, 3 더하기 4

문제 링크

15989번: 1, 2, 3 더하기 4

---

주의사항

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

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

---

문제 설명

---

접근 방법

동적 계획법

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

 

이 문제에 핵심은

 

1. 1, 2, 3의 합으로 n을 만들 수 있는 방법의 수를 결과로 출력합니다.

2. 합의 순서만 다른 것은 같은 것으로 판정한다.

 

 

알고리즘 진행 순서.

 

1. 입력되는 T개의 n을 저장합니다.

 

2. 점화식을 이용해서 1~10000까지의 DP[][]을 저장합니다.

 

3. 해당 DP[n][1] + DP[n][2] + DP[n][3]의 값을 결과로 출력한다.

 

 

점화식

 

DP[n][1] = DP[n-1][1]

 

DP[n][2] = DP[n-2][1] + DP[n-2][2]

 

DP[n][3] = DP[n-3][1] + DP[n-3][2] + DP[n-3][3]

 

DP[n][1]의 해석

n의 값을 1, 2, 3의 합의 순서를 오름차순으로 나타날 때 마지막 값이 1인 개수

Ex.

DP[1][1] = (1)

DP[2][1] = (1 + 1)

DP[4][1] = (1 + 1 + 1 + 1)

 

DP[n][2]의 해석

n의 값을 1, 2, 3의 합의 순서를 오름차순으로 나타날 때 마지막 값이 2인 개수

Ex.

DP[1][2] = ()

DP[2][2] = (2)

DP[4][2] = (1 + 1 + 2), (2 + 2)

 

DP[n][3]의 해석

n의 값을 1, 2, 3의 합의 순서를 오름차순으로 나타날 때 마지막 값이 3인 개수

Ex.

DP[1][3] = ()

DP[3][3] = (3)

DP[4][3] = (1 + 3)

 

점화식이 나오는 이유.

 

DP[n][1] = DP[n-1][1]

DP[n][1]에서 n을 만들때 항상 마지막에 1을 사용합니다.

합의 연산을 오름차순으로 나타내기 때문에 마지막 숫자가 가장 큰 숫자입니다.

즉, 1보다 큰 숫자가 들어가면 안되고 마지막에 항상 1이 사용되는 개수 : DP[n-1][1]

DP[5][1] =  ......(4)  + 1

....(4)의 들어갈 수 있는 것 :  DP[4][1]

 

DP[n][2] = DP[n-2][1] + DP[n-2][2]

DP[n][2]에서 n을 만들때 항상 마지막에 2을 사용합니다.

합의 연산을 오름차순으로 나타내기 때문에 마지막 숫자가 가장 큰 숫자입니다.

즉, 2보다 큰 숫자가 들어가면 안되고 마지막에 항상 2가 사용되는 개수 : DP[n-2][1] + DP[n-2][2]

DP[5][1] =  ......(3)  + 2 

....(3)의 들어갈 수 있는 것 :  DP[3][1], DP[3][2]

 

DP[n][3] = DP[n-3][1] + DP[n-3][2] + DP[n-3][3]

DP[n][2]에서 n을 만들때 항상 마지막에 2을 사용합니다.

합의 연산을 오름차순으로 나타내기 때문에 마지막 숫자가 가장 큰 숫자입니다.

즉, 2보다 큰 숫자가 들어가면 안되고 마지막에 항상 2가 사용되는 개수 : DP[n-3][1] + DP[n-3][2] + DP[n-3][3]

DP[5][1] =  ......(2)  + 3 

....(2)의 들어갈 수 있는 것 :  DP[2][1], DP[2][2], DP[2][3]

 

Ex.

DP[1][1] = (1)

DP[1][2], DP[1][3] = ()

 

DP[2][1] = (1 + 1)

DP[2][2] = (2)

DP[2][3] = ()

 

DP[3][1] = (1 + 1 + 1)

DP[3][2] = (1 + 2)

DP[3][3] = (3)

 

DP[4][1] = (1 + 1 + 1 + 1)

DP[4][2] = (1 + 1 + 2), (2 + 2)

DP[4][3] = (1 + 3)

...

 

예제입력 1.

 

1. 입력되는 T개의 n을 저장합니다.

 

T = 3

 

n₁ = 4

n₂ = 7

n₃ = 10

 

2. 점화식을 이용해서 1~10000까지의 DP[][]을 저장합니다.

 

※예제입력1에서 최대 10까지 찾아보기 때문에 10까지만 구해보겠습니다.

 

DP[n][1] = DP[n-1][1]

DP[n][2] = DP[n-2][1] + DP[n-2][2]

DP[n][3] = DP[n-3][1] + DP[n-3][2] + DP[n-3][3]

 

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

 

3. 해당 DP[n][1] + DP[n][2] + DP[n][3]의 값을 결과로 출력한다.

 

n₁ = 4

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

 

n₂ = 7

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

 

n₃ = 10

DP[10][1] + DP[10][2] + DP[10][3] = 1 + 5 + 8 = 14

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• DP[1][], DP[2][], DP[3][]의 값을 초기화하는 init 함수를 실행하였습니다.
• getDP함수를 실행하여 DP[4...10000][]의 값을 저장하였습니다.
• 각 n의 값마다 DP[n][1] + DP[n][2] + DP[3]의 값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• init는 가장 왼쪽 칸에서 각 칸에 정수에 따라 점프하는 것을 이용하여 BFS탐색하는 함수입니다.
• getDP는 점화식을 이용하여 DP[4....10000][]의 값을 모두 구하는 함수입니다.

 

import java.util.*;
import java.io.*;
public class Main {
    static int[][] DP = new int[10001][4];	//메모이제이션 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        init();	//DP[1][], DP[2][], DP[3][]을 초기화
        getDP();	//DP[][] 4....10000의 값 메모이제이션에 저장하기
        int T = Integer.parseInt(br.readLine());
        //T개의 n(DP[n][1] + DP[n][2] + DP[n][3]의 값을 BufferedWriter 저장
        for(int i=0;i<T;i++){
            int N = Integer.parseInt(br.readLine());
            int result = DP[N][1] + DP[N][2] + DP[N][3];
            bw.write(result + "\n");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //점화식을 이용하여 4...10000의 DP값 구해서 저장하는 함수
    static void getDP(){
        for(int i=4;i<10001;i++){
            DP[i][1] = DP[i-1][1];
            DP[i][2] = DP[i-2][1] + DP[i-2][2];
            DP[i][3] = DP[i-3][1] + DP[i-3][2] + DP[i-3][3];
        }
    }
    //DP[1][], DP[2][], DP[3][]을 초기화하는 함수
    static void init(){
        DP[1][1] = DP[2][1] = DP[2][2] = DP[3][1] = DP[3][2] = DP[3][3] = 1;
    }
}