[자바] 백준 24395 - 명진이의 신년계획 (java)

목차

문제 : boj24395

 

 

필요 알고리즘

• DP, 냅색
  
  • 흔히 냅색이라 부르는 유형의 DP 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  기본적인 냅색 문제인데, 2차원으로 진행된다는 점만 주의하면 된다.

dp[x][y]를 빨강 알약 x개, 파란 알약 y로 처방 가능한 위험도의 최대치라고 하자.

이 경우 처방할 빨강, 파랑 알약의 수가 r과 b라고 한다면, dp[x][y] = max(dp[x][y], dp[x-r][y-b]) 이 된다.

이걸 모든 처방 M개에 대해 반복해주면 되는 냅색문제이다.

 

  냅색에서 주의점은 처방할 알약이 여러개가 가능하다면, x와 y를 작은 수치부터 시작해서 계속 중첩해나가도 되지만, '하나의 질병에 대해 여러 번 처방받을 수 없다.' 라는 조건이 있으므로 x와 y를 높은 수치부터 시작해야 현재 처방이 여러번 중복되지 않게 된다.

for (int i = LIMIT; i >= 0; i--) {
    for (int j = LIMIT; j >= 0; j--) {
        if (i < r || j < b || dp[i-r][j-b] == -1) continue;

        dp[i][j] = max(dp[i][j], dp[i-r][j-b] + d);
    }
}

 

  그리고 내 경우 메모리초과를 많이 받았는데, 별 생각없이 처방받는 알약의 수가 50종류이고 위험도가 최대 100 이므로 5000 x 5000 짜리 dp 배열을 만들어서 그랬다 ㅠ. 어차피 N명의 학생의 R, B값이 최대 50이므로 50x50 배열로 진행하고, 51 이상의 위험도는 버리면 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Math.max;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    static final int LIMIT = 50;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] dp = new int[LIMIT+1][LIMIT+1];
        for (int[] row : dp) Arrays.fill(row, -1);
        dp[0][0] = 0;

        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            for (int i = LIMIT; i >= 0; i--) {
                for (int j = LIMIT; j >= 0; j--) {
                    if (i < r || j < b || dp[i-r][j-b] == -1) continue;

                    dp[i][j] = max(dp[i][j], dp[i-r][j-b] + d);
                }
            }
        }

        List<int[]> target = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            target.add(new int[]{i,max(0,dp[r][b])});
        }

        Collections.sort(target, new Comparator<int[]>() {
            @Override
            public int compare(final int[] o1, final int[] o2) {
                if (o1[1] == o2[1])
                    return o1[0] - o2[0];
                return o1[1] - o2[1];
            }
        });

        StringBuilder answer = new StringBuilder();
        for (int[] cur : target) {
            answer.append(cur[0]).append(' ').append(cur[1]).append('\n');
        }
        System.out.print(answer);
    }
}