17845번 - 수강 과목

2024-05-14

#JAVA#백준

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
첫줄에 최대 공부시간 N, 과목수 K가 주어진다.

•
K개의 줄에 중요도, 필요한 공부시간이 주어진다.

•
공부 시간의 한계를 초과하지 않으며 과목의 중요도 합이 최대가 되도록 선택해서 수강하자.

문제 풀이

오랜만에 백팩 알고리즘이 생각나서 풀어보았는데

안푼지 꽤 오래 됐더니 간단한 동작 방식만 기억났고

제대로 된 알고리즘 동작 방식이 생각나지 않았다.

결국 다시 블로그를 참조해서 기억을 더듬어 풀 수 있었다.

C++

위와 같은 입력을 하면 아래와 같은 표가 만들어진다.

정답 코드

Java

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

public class Main {
    public static int arr[][], input[][];
    public static int n, k;

    public static void dp() {
        for (int i = 1; i <= k; i++) {
            int time = input[i][1]; //현재 과목의 수강 시간
            int imp = input[i][0];  //현재 과목의 중요도
            for (int j = 1; j <= n; j++) {
                if (j < time) {  //현재 시간이 과목의 수강시간보다 작으면 이전 과목에서의 중요도 복사
                    arr[i][j] = arr[i - 1][j];
                }
                else { //아니면 현재 과목을 수강했을 때 최대 중요도와 수강하지 않았을 때 중요도 비교
                    arr[i][j] = Math.max(arr[i - 1][j], imp + arr[i - 1][j - time]);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        arr = new int[k + 1][n + 1];
        input = new int[k + 1][2];

        for (int i = 1; i <= k; i++) {
            st = new StringTokenizer(br.readLine());
            input[i][0] = Integer.parseInt(st.nextToken());
            input[i][1] = Integer.parseInt(st.nextToken());
        }
        
        dp();

        System.out.println(arr[k][n]);
    }
}

풀고 보니 코드가 그렇게 어렵지 않았따.

알고리즘 동작 방식만 이해하면 굉장히(?) 쉬운 문제인 것 같다.