문제
https://www.acmicpc.net/problem/12865
풀이
[Algorithm] 동적 계획법(Dynamic Programming)
작성 이유 [Programmers] 완전범죄 - Java문제 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제 좀 어려웠다...처음에는 이
gretea5.tistory.com
을 참고해서 풀이를 작성하겠다.
1. 어려운 문제가 될 수 있는 요소 찾기
물건
무게(w)
가치(v)
준서가 넣는 물건들 중 k 이하의 무게로 넣었을때 얻을 수 있는 최대의 가치이다.
결국 어려운 문제가 되려면 물건을 고르고, 최대 무게(w)가 되었을때가 어려운 문제라고 말할 수 있을 것이다.
최대 무게
물건을 고름
2. 테이블 정의
dp[i][j] = i번째 물건을 넣었을 때, 정확히 j의 무게로 담았을 때의 최대 가치로 정의했다.
3. 정의한 테이블에서 정답을 찾기
물건이 n개 있다고 한다면, n개의 물건을 넣은 dp[i][0] ~ dp[i][k] 까지의 가치들중 최대 가치를 구하면 된다고 생각했다.
4. 정의한 테이블에서 초기화
물건을 아예 넣지 않은 경우에 대해 담았을 경우, 얻을 수 있는 가치는 0인데,
java에서 int 배열을 선언하면 기본적으로 0이므로, 초기화 로직이 없어도 된다.
5. 점화식 도출
이 문제에서 물건을 넣는가/물건을 안넣는가가 문제에 상황에서 변화될 수 있는 요소이다.
물건을 넣지 않는다면
=> dp[i - 1][j] : 정확히 j 무게로 담는데, i - 1번의 물건을 담았을 경우의 가치
물건을 넣는 다면
=> dp[i - 1][j - w] + v : 물건에는 무게가 있다. 그러면 기존 가방에 대한 무게는 담는 물건에 대한 무게를 뺀, j - w가 될 것이고, 물건을 담지 않았기 때문에, dp[i - 1][j - w]이다 여기에 가치(v)를 더한 가치이다.
주의
j - w가 0보다 작을 수도 있다. 현재 가방의 무게보다 물건의 무게가 더 커질 수 있으므로, 0보다 작아질 수 있음에 유의한다.
그래서 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 무게] + 가치)이다.
소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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[] w = new int[n + 1];
int[] v = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
st = new StringTokenizer(br.readLine(), " ");
w[i] = Integer.parseInt(st.nextToken());
v[i] = Integer.parseInt(st.nextToken());
}
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < k + 1; j++) {
dp[i][j] = dp[i - 1][j];
//j의 무게를 담을 수 있는 가방에서, 무게를 넣을 수 있을 때,
if (j - w[i] >= 0) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}
int answer = Integer.MIN_VALUE;
for (int value : dp[n]) {
answer = Math.max(value, answer);
}
System.out.print(answer);
br.close();
}
}'Problem Solving > Baekjoon' 카테고리의 다른 글
| [Baekjoon] 과일 탕후루 - Java (0) | 2025.08.21 |
|---|---|
| [Baekjoon] 올림픽 - Java (0) | 2025.08.17 |
| [Baekjoon] 백준 1092: 배 - Java (0) | 2024.10.17 |
| [Baekjoon] 백준 7662: 이중 우선순위 큐 - Java (0) | 2024.09.22 |
| [Baekjoon] 백준 9935: 문자열 폭발 - Java (0) | 2024.09.19 |