[백준, Java] 16195번, 1, 2, 3 더하기 9(DP)

문제 링크

16195번: 1, 2, 3 더하기 9

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 1, 2, 3을 m개 이하의 합으로 n을 만드는 방법의 개수를 결과로 출력합니다.

2. 방법의 수를 1,000,000,009로 나눈 나머지를 출력합니다.

3. 1 + 2 + 1, 1 + 1 + 2는 다른 방법입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 점화식을 통한 결과를 메모이제이션을 통해 방법의 개수를 구합니다.

 

3. 구한 방법의 개수를 결과로 출력합니다.

 

 

점화식

 

DP[i][j]

i : 1, 2, 3으로 만들어야 하는 합의 값

j : 1, 2, 3을 사용할 수 있는 개수

 

Ex.

DP[4][3] : 1, 2, 3을 3번 사용한 합으로 4을 만들 수 있는 방법의 개수

 

	1	2	3
0	0	0	0
1	1	0	0
2	1	1	0
3	1	2	1
4	0	3	3

 

DP[1][1] : (1)

 

DP[2][1] : (2)

DP[2][2] : (2)

 

DP[3][1] : (3)

DP[3][2] : (1 + 2), (2 + 1)

DP[3][3] : (1)

 

DP[4][j]의 관련된 내용을 정의할 때

 

DP[4][2]를 구할 때

 

1을 항상 사용할 때 방법의 개수: DP[3][1]

2을 항상 사용할 때 방법의 개수 : DP[2][1]

3을 항상 사용할 때 방법의 개수 : DP[3][1]

 

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

위와 같이 구할 수 있습니다.

 

이를 점화식으로 표현하면

 

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

 

 

예제입력 1.

※ 테스트케이스 2번을 기준으로 보여드리겠습니다.

1. 입력된 정보를 저장합니다.

 n : 7

 

m : 5

 

2. 점화식을 통한 결과를 메모이제이션을 통해 방법의 개수를 구합니다.

 

점화식을 통해 계산 진행

 

	1	2	3	4	5
0	0	0	0	0	0
1	1	0	0	0	0
2	1	1	0	0	0
3	1	2	1	0	0
4	0	3	3	1	0
5	0	2	6	4	1
6	0	1	7	10	5
7	0	0	7	16	15

 

3. 구한 방법의 개수를 결과로 출력합니다.

 

 

7을 만들 때 사용하는 방법의 개수

 

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

 

= 0 + 0 + 7 + 16 + 15 = 37

 

 

 

방법의 개수 37을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 n과 m을 띄어쓰기 기준으로 나누었습니다.
• 점화식으로 모든 경우를 미리 DP[][]에 구성합니다.
• 각 TestCase의 DP[n][1] + ... + DP[n][m]의 합으로 방법의 개수를 구합니다.
• 구한 방법의 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static final int REMAIN_VALUE = 1000000009;	//나머지를 진행할 값
    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));
        //테스트 케이스 개수 저장
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //모든 DP[][]경우를 점화식을 통해 미리 계산
        long[][] DP = new long[1001][1001];
        DP[1][1] = DP[2][1] = DP[3][1] = DP[2][2] = DP[3][3] = 1L;
        DP[3][2] = 2L;
        //점화식을 통한 계산
        for(int i=4;i<1001;i++){
            for(int j=2;j<1001;j++)
                DP[i][j] = (DP[i-1][j-1] + DP[i-2][j-1] + DP[i-3][j-1]) % REMAIN_VALUE ;
        }
        //각 테스트 케이스 진행
        for(int tc=0;tc<T;tc++){
            st = new StringTokenizer(br.readLine()," ");
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            long result = 0L;
            //DP[n][1] + ... + DP[n][m] 진행
            for(int i=1;i<=m;i++) {
                result = (result+ DP[n][i]) % REMAIN_VALUE;
            }
            bw.write(String.valueOf(result));	//방법의 개수 BufferedWriter 저장
            bw.newLine();
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}