백준/배낭 문제
17845 수강 과목
have a good time
2022. 6. 5. 21:38
1. 풀이
배낭 문제 알고리즘을 사용하면 된다.
이에 대한 설명은 다음 글에 자세하게 설명해 놓았다.
https://happy-fun.tistory.com/246
12865 평범한 배낭
1. 배낭 문제 알고리즘 배낭 문제 알고리즘을 이용해서 풀면 된다. 배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때, 일정한 가치, 무게가 정해져 있는 짐들을 배낭에 담아야 한
happy-fun.tistory.com
2. 최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int subject [][] = new int[K+1][2];
for(int i=1; i<=K; i++) {
st = new StringTokenizer(br.readLine(), " ");
subject[i][0] = Integer.parseInt(st.nextToken());
subject[i][1] = Integer.parseInt(st.nextToken());
}
int dp[][] = new int[K+1][N+1];
for(int i=1; i<=K; i++) {
for(int j=1; j<=N; j++) {
if(j>=subject[i][1]) {
dp[i][j] = Math.max(dp[i-1][j], subject[i][0] + dp[i-1][j-subject[i][1]]);
}else {
dp[i][j] = dp[i-1][j];
}
}
}
System.out.println(dp[K][N]);
}
}