ALGORITHM/BOJ
[백준] 14728 벼락치기
0298
2021. 1. 7. 11:48
14728번: 벼락치기
ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와
www.acmicpc.net
2021-01-07
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main14728 {
public static int N, T, time[], points[] , dp[][];
public static void solve() {
for(int i = 1; i <= N; i++) {
for(int p = 0; p <= T; p++) {
if(p - time[i] < 0) dp[i][p] = dp[i-1][p];
else dp[i][p] = Math.max(dp[i-1][p], dp[i-1][p-time[i]] + points[i]);
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
time = new int[N+1];
points = new int[N+1];
dp = new int[N+1][T+1];
for(int i = 1; i <= N; i++) {
st = new StringTokenizer(bf.readLine());
time[i] = Integer.parseInt(st.nextToken());
points[i] = Integer.parseInt(st.nextToken());
}
solve();
System.out.println(dp[N][T]);
}
}
|
cs |
#문제풀이
0/1 knapsack 문제로, 복습 차원에서 풀어봤다.
아래 문제와 같은 방법으로 풀면된다.
[백준] 12865 평범한 배낭
www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤..
void2017.tistory.com
다른 점은 '평범한 배낭' 문제는 값을 2차원 배열로 저장했었는데, 이번에는 time과 points 각각 다른 1차원 배열로 저장했다.