[Java / 백준] 4781. 사탕 가게

문제

 

풀이

이 문제는 knapsack으로 풀 수 있는 문제인데, 그렇게 하기 위해서는 행의 인덱스는 사탕의 번호를, 열의 인덱스는 현재까지 쓴 비용을 나타내도록 하는 배열을 선언해주어야 합니다.
그런데 이 문제의 경우, 비용이 소수 2자리까지 있는 실수로 입력되므로, 100을 곱해서 정수로 바꿔서 문제를 해결했습니다.

즉, n: 사탕의 종류, m: 비용, M: m에 100을 곱한 수라고 한다면

dp[n][M]에는 n번째 사탕까지 고려했을 때, M원을 썼을 때에 최대 칼로리가 담기게 됩니다.

 

1. 입력 받기

int n, m;
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = (int)Math.round((Double.parseDouble(st.nextToken()) * 100.0));

if(n == 0) break; // 종료

int[][] dp = new int[n+1][m+1]; // 담기는 수: 칼로리

ArrayList<int[]> list = new ArrayList<>();
list.add(new int[] {0, 0});
for(int i=1; i<=n; ++i) {
  st = new StringTokenizer(br.readLine());
  int a = Integer.parseInt(st.nextToken());
  int b = (int)Math.round((Double.parseDouble(st.nextToken()) * 100.0));
  list.add(new int[] {a, b});
}

n과 m을 입력 받습니다.
이때 m은 소수 2째 자리까지의 실수이므로 m에 100을 곱해서 정수로 만든 다음 (int)로 캐스팅 해줍니다.
이때 주의해야할 점은 부동소수점의 오차때문에 아래 코드처럼 바로 (int)로 캐스팅해주면 답이 틀릴 수 있습니다.

m = (int)(Double.parseDouble(st.nextToken()) * 100.0);

예를들어, 부동 소수점 오차때문에 3.34라는 수에 100.0을 곱한 수가 334.0가 아닌 333.9999xx 이런식으로 될 수 있습니다.
333.999xx 이 수에 (int)로 캐스팅을 하면 버림을 하기 때문에, 결과가 334가 아닌 333이 되는 것입니다.

따라서 아래처럼 Math.round()로 반올림을 해준 뒤, (int)로 캐스팅 해주어야 원하는 결과를 얻을 수 있습니다.

n, m을 입력 받은 뒤, 아래 n개의 줄에서 입력으로 들어오는 사탕의 칼로리와 비용은 list에 저장해주었습니다.

 

2. dp 배열 채우기

for(int i=1; i<=n; ++i) {
  for(int j=0; j<=m; ++j) {
    if(j - list.get(i)[1] >= 0) {
      dp[i][j] = Math.max(dp[i][j-list.get(i)[1]] + list.get(i)[0], dp[i-1][j]);
    } else {
      dp[i][j] = dp[i-1][j];
    }
  }
}

반복문을 돌며 dp 배열을 채워줍니다.
dp[i][j]에 들어갈 수 있는 값은 j - (i번째 사탕의 값)이 0이상인지 아닌지에 따라 달라집니다.

(i) j - (i번째 사탕의 값) < 0 인 경우:
이 경우는 j원을 가지고 i번째 사탕을 하나도 살 수 없는 경우입니다.
따라서 (i-1)번째 사탕까지 고려했을 때, j원으로 살수 있는 사탕의 최대 칼로리를 넣어줍니다.

dp[i][j] = dp[i-1][j];

(ii) j - (i번째 사탕의 값) >= 0 인 경우
이 경우는 j원을 가지고 i번째 사탕을 살 수 있는 경우입니다.
따라서 이 경우는 i번째 사탕을 사는 경우와 사지 않는 경우 중 최대 값을 dp 배열에 담아줍니다.

dp[i][j] = Math.max(dp[i][j-(i번째 사탕의 가격)] + (i번째 사탕의 가격), dp[i-1][j]);

 

3. 정답 출력하기

bw.write(dp[n][m] + "\n");

위 과정을 거치면 dp[n][m]에 들어있는 값이 m원을 썼을 때 살수 있는 사탕의 최대 칼로리 수가 됩니다.

 

전체 코드

import java.io.*;
import java.util.*;

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    while(true) {
      int n, m;
      StringTokenizer st = new StringTokenizer(br.readLine());
      n = Integer.parseInt(st.nextToken());
      m = (int)Math.round((Double.parseDouble(st.nextToken()) * 100.0));

      if(n == 0) break; // 종료

      int[][] dp = new int[n+1][m+1]; // 담기는 수: 칼로리

      ArrayList<int[]> list = new ArrayList<>();
      list.add(new int[] {0, 0});
      for(int i=1; i<=n; ++i) {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = (int)Math.round((Double.parseDouble(st.nextToken()) * 100.0));
        list.add(new int[] {a, b});
      }

      for(int i=1; i<=n; ++i) {
        for(int j=0; j<=m; ++j) {
          if(j - list.get(i)[1] >= 0) {
            dp[i][j] = Math.max(dp[i][j-list.get(i)[1]] + list.get(i)[0], dp[i-1][j]);
          } else {
            dp[i][j] = dp[i-1][j];
          }
        }
      }

      bw.write(dp[n][m] + "\n");
    }

    bw.flush();
  }

}