사탕 가게(백준_4781)

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

4781번: 사탕 가게

문제 설명

상근이가 가지고 있는 돈으로 사탕을 살 때, 칼로리를 최대로 만들어라!

• 사탕은 쪼갤 수 없기 때문에, 일부만 구매할 수 없다.
• 사탕은 원하는 만큼 구매할 수 있도록 충분히 주어진다.
• 돈의 양이 소수점 둘째 자리로 주어진다.

 

문제에 대한 아이디어

다이나믹 프로그래밍 문제로 아주 유명한 배낭 문제와 비슷해 보인다. 사탕을 원하는 만큼 구매할 수 있다는 부분에서 난이도를 낮춰 주었지만 돈의 양이 소수점이라는 점에서 난이도가 올라갔다. 소수점을 처리하는 부분에서 고생을 했다.

 

DP를 이용해서 풀기

문제의 예시를 토대로 설명할려고 한다. (소수점 없다 하고 설명)

제일 처음 내가 가지고 있는 돈의 수+1 만큼 배열을 만든다. 예시에서는 8이므로 크기 9의 배열을 만든다. 

7원으로 살 수 있는 사탕의 칼로리는 700이다.  그러므로 7원보다 높은 인덱스는 모두 700원으로 한다.

2번째에는 3원으로 299원 짜리 칼로리의 사탕을 살 수 있다. 그러므로 인덱스 3부터 299을 채워 나간다. 하지만 6에서는 299원 짜리 2개를 살 수 있으므로 칼로리 588을 만들 수 있다. 그 후 7, 8에 서는 첫번째에서 크기와 비교해 더 큰 칼로리를 선택한다. 

3번째에는 5원으로 칼로리 499 사탕을 살 수 있다. 인덱스 5부터 비교해나가면 인덱스 8에서 3원짜리 299원가 합쳐 798원짜리를 살 수 있다.

 

점화식

Math.max(arr[idx], arr[idx-(현재 사탕의 가격)] + 현재 사탕의 칼로리)

 

소수점 둘째 자리 처리하기

위에 문제에서 사탕의 가격을 배열의 인덱스로 사용하여 문제를 풀기 때문에 소수점 둘째자리로 문제를 해결할 수 없다. 소수점 둘째자리를 정수로 처리해줘야 한다. 

제일 처음 정수로 처리하기 위해 double로 받고 100을 곱해 준뒤 int로 캐스팅 해주었다.  하지만 계속 틀렸다.

찾아 보니 int로 캐스팅 하기전에 0.5를 더해줘야 한다고 한다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double n = sc.nextDouble();
        n*=100;
        int result = (int) n;
        System.out.println("result = " + result);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double n = sc.nextDouble();
        n*=100;
        System.out.println("n = " + n);
        n+=0.5;
        int result = (int) n;
        System.out.println("result = " + result);
    }
}

 

구현

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

public class 백준_4781 {
    public static void main(String [] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sub = new StringBuffer();
        while(true){
            StringTokenizer st = new StringTokenizer(buf.readLine());
            int n = Integer.parseInt(st.nextToken());
            double temp_m = Double.parseDouble(st.nextToken());
            temp_m *= 100; temp_m += 0.5;
            int m = (int) temp_m;
            if(n==0 && m== 0) break;
            int dp[] = new int[m + 1];
            for(int i=0; i<n; ++i) {
                st = new StringTokenizer(buf.readLine());
                int calorie = Integer.parseInt(st.nextToken());
                double temp = Double.parseDouble(st.nextToken());
                temp *= 100; temp += 0.5;
                int num = (int) temp;
                if(num > m) continue; //사탕의 가격이 가지고 있는 돈 보다 크면 넘김
                //다이나믹 프로그래밍을 하는 부분
                for (int j = num; j < m + 1; ++j) {
                    dp[j] = Math.max(dp[j], dp[j - num] + calorie);
                }
            }
            sub.append(dp[m] +"\n");
        }
        System.out.print(sub);
    }
}

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_4781.java

GitHub - Heron-Woong/CodingTest_Practice