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

문제 링크

11052번: 카드 구매하기

---

주의사항

• 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	5	6	10
3(6)	0	1	5	6	10
4(7)	0	1	5	6	10

 

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

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

P₁ 1개 구매

 

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

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

P₁, P₂ 1개씩 구매

 

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

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

P₂ 2개 구매

 

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

 

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

 

규칙을 살펴보면

row값 <= col값일 때

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

 

row값 > col값일 때

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

 

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

 

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

(1, 1)을 구할 때

row(1) <= col(1)이므로

DP[1][1] = Math.max(DP[0][1], cardCost[1] + DP[1][0])

DP[1][1] = Math.max(0, 1) = 1

 

(3, 2)을 구할 때

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

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

 

(3, 4)을 구할 때

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

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

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

 

문제에 해결알고리즘은

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

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

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

 

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

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

 

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N;	//카드 구매 개수
	public static int[] cardCost;	//카드팩 비용 저장 배열
	public static int[][] DP;		//메모이제이션
    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());
    	cardCost = new int[N+1];
    	DP = new int[N+1][N+1];
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	for(int i=1;i<=N;i++)
    		cardCost[i] = Integer.parseInt(st.nextToken());
    	
    	cardBuy();		//함수 실행
    	bw.write(DP[N][N] + "\n");	//DP[N][N]값 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //규칙대로 DP 구성하는 함수
    public static void cardBuy() {
    	for(int i=1;i<=N;i++) {
    		for(int j=1;j<=N;j++) {
    			if(j<=i) {		//row <= col 일 때
    				DP[j][i] = Math.max(cardCost[j] + DP[j][i-j], DP[j-1][i]);
    			}else {		// row > col일 때
    				DP[j][i] = DP[j-1][i];
    			}
    		}
    	}
    	return;
    }
}