[백준] code.plus(다이나믹 프로그램 part 1,JAVA)16194번, 카드 구매하기 2

문제 링크

16194번: 카드 구매하기 2

---

주의사항

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

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

---

문제 설명

---

접근 방법

다이나믹 프로그램

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

 

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

 

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

 

이 문제에 핵심은

1. 카드팩은 N개가 있다.

2. 각 카드팩 인덱스만큼 카드가 들어가있다.

3. N개의 카드를 구하기위한 지불 최소값을 출력한다.

 

배열

 

DP : 메모이제이션 배열

 

cardCost : 카드팩 비용을 저장하는 배열

 

냅색 알고리즘과 DP 배열을 이용하여 최대 지불액을 구하였습니다.

 

표를 이용하여 표현하면 규칙을 찾을 수 있습니다.

 

예제입력1의 내용을 냅색 알고리즘의 표로 표현하면(row = 카드팩 비용, col = 구매 카드 개수)

	0	1	2	3	4
0	0	0	0	0	0
1(1)	0	1	2	3	4
2(5)	0	1	2	3	4
3(6)	0	1	2	3	4
4(7)	0	1	2	3	4

 

(1, 1)이 나타내는 값은

카드를 1개 구입할 때 카드팩의 종류가 P₁ = 1인 카드팩만 존재할 때 최대 지불액 = 1

P₁ 1개 구매

 

(2, 3)이 나타내는 값은

카드를 3개 구입할 때 카드팩의 종류가 P₁ = 1, P₂ = 5인 카드팩만 존재할 때 최대 지불액 = 3

P₁ 3개 구매

 

(3, 4)이 나타내는 값은

카드를 4개 구입할 때 카드팩의 종류가 P₁ = 1, P₂ = 5, P₃ = 6인 카드팩만 존재할 때 최대 지불액 = 4

P₁ 4개 구매

 

(4, 4)가 나타내는 값은문제에서 찾고 있는 N = 4이고 카드팩 종류도 모두 포함하는 최소 지불액입니다.

 

DP(N, N)을 결과로 출력하면 됩니다.

 

규칙을 살펴보면

row값 <= col값일 때

DP[row][col] = Math.min(DP[row-1][col], cardCost[row] + DP[row][col-row])

 

row값 > col값일 때

DP[row][col] = DP[row-1][col]

 

2가지로 표현할 수 있습니다.

 

해당 규칙을 표에 적용해보면

 

(3, 2)을 구할 때

row(3) > col(2)이므로

DP[3][2] = DP[2][2] = 2

 

(3, 4)을 구할 때

row(3) <= col(4)이므로

DP[3][4] = Math.min(DP[2][4], cardCost[3] + DP[3][1])

DP[3][4] = Math.min(4, 7) = 4

 

(1, 1)을 적용할 때 row나 col인덱스가 0이 되어 최소 비용값을 구할 때 0이 저장될 수 있습니다.

그래서 저는 (1,1) ~ (1, 4)를 먼저 초기화한 뒤 규칙에 맞는 알고리즘으로 DP[][]를 구성해주었습니다.

 

문제에 해결알고리즘은

1. N과 카드팩 비용을 받습니다.

2. 위에 규칙대로 반복문을 통해 DP[][]를 구성합니다.

3. DP[N][N]이 문제에 원하는 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• 반복문을 통해 규칙을 적용하여 DP[][]를 구성하는  buyCard함수를 만들었습니다.
• BufferedWriter에 DP[N][N]을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• buyCard는 규칙을 통한 반복문으로 DP[][]를 구성하였습니다.

 

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N;		//카드 구매 개수
	public static int[][] DP;		//메모이제이션
	public static int[] cardCost;		//카드팩 비용 저장 배열
    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
        //---------입력값 저장 및 배열 초기화---------
    	N = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	cardCost = new int[N+1];
    	for(int i=1;i<=N;i++) {
    		cardCost[i] = Integer.parseInt(st.nextToken());
    	}
    	DP = new int[N+1][N+1];
        /*
        (1, 1) ~ (1, 4)는 규칙을 적용하면 row나 col이 0이 되어
        최소값을 저장할 때 0이 저장될 수 있습니다.
        먼저 값을 구해서 저장한 뒤 함수를 실행하도록 하였습니다.
        */
    	for(int i=1;i<=N;i++) {
    		DP[1][i] = cardCost[1] * i;
    	}
    	buyCard();		//함수 실행
    	bw.write(DP[N][N] + "\n");		//DP[N][N] BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //------규칙을 통해 DP를 구성하는 함수--------
    public static void buyCard() {
    	for(int i=1;i<=N;i++) {
    		for(int j=2;j<=N;j++) {
    			if(j<=i) {		//row <= col 일 때
    				DP[j][i] = Math.min(DP[j-1][i], cardCost[j] + DP[j][i-j]);
    			}else {		//row > col일 때
    				DP[j][i] = DP[j-1][i];
    			}
    		}
    	}
    	return; 	
    }
}