[DP] 백준 알고리즘 4781번 사탕가게

문제 : https://www.acmicpc.net/problem/4781

Github : https://github.com/ddulhddul/algorithm/blob/master/src/Baekjoon4781.java

1. DP 이용해 풀었음.

2. 가격을 기준으로 한단계 전 케이스를 고려해서 탐색

소스코드

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Baekjoon4781 {
//public class Main {
	
	public static void main(String[] args) 
			throws FileNotFoundException 
	{

		File file =new File("D:\\dev\\worksspace\\Solution\\src\\Baekjoon4781");
		Scanner sc = new Scanner(file);
//		Scanner sc = new Scanner(System.in);
		
		while (sc.hasNext()) {
			
			int candyTypeNum = sc.nextInt();
			int avlMoney = (int)Math.round(sc.nextDouble()*100);
			
			if(candyTypeNum == 0 && avlMoney == 0) break;
			
			int[] candyCal = new int[candyTypeNum];
			int[] candyPrice = new int[candyTypeNum];
			
			for (int i = 0; i < candyTypeNum; i++) {
				candyCal[i] = sc.nextInt();
				candyPrice[i] = (int)Math.round(sc.nextDouble()*100);
				
			}
			
			int[] d = new int[avlMoney+1]; // 남은금액이 ~ 일때, 최대칼로리
			for (int i = 0; i <= avlMoney; i++) {
				for (int j = 0; j < candyTypeNum; j++) {
					if(i-candyPrice[j] >= 0){
						d[i] = Math.max(d[i], d[i-candyPrice[j]] + candyCal[j]);
					}
				}
			}
			
			System.out.println(d[avlMoney]);
		}
		
	}
}