백준 17845번 - 수강 과목 자바 풀이

문제 링크

문제 풀이 시간 : 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]);
    }
}

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

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

17845번 - 수강 과목

문제 풀이 시간 : 1시간

문제 요약

문제 풀이

정답 코드

함께 읽으면 좋은 글

5430번 - AC

1966번 - 프린터 큐

1158 - 요세푸스 문제

2164번 - 카드2