백준 14728 - 벼락치기

Java

14728 번 - 벼락치기

문제

접근 방법

Knapsack 알고리즘으로 해결하였다.

시간을 무게로, 점수를 금액으로 생각하여 품

코드

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

public class Main {
	static int n, m, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	int[][] dp = new int[n + 1][m + 1];
    	int[] time = new int[n + 1];
    	int[] score = new int[n + 1];

    	for(int i = 1; i <= n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		time[i] = stoi(stk.nextToken());
    		score[i] = stoi(stk.nextToken());
    	}

    	int t, s;
    	// 과목 선택
    	for(int i = 1; i <= n; i++) {
    		// 시간이 흘러감
    		for(int j = 1; j <= m; j++) {
    			t = time[i];
    			s = score[i];

    			dp[i][j] = dp[i - 1][j];	// 현재 시간을 넣지 않았을 때
    			// 현재 시간이 해당 과목을 공부하기에 충분하면
    			if(j >= time[i]) {
    				dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - t] + s);
    			}
    		}
    	}
    	System.out.println(dp[n][m]);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점