[백준] 12865 - 평범한 배낭 (JAVA)

1. 소요시간 : 40분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 5
4. 문제 유형 : 다이나믹 프로그래밍 , 배낭 문제
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : O
7. 문제 링크 : https://www.acmicpc.net/problem/12865
8. 푼 날짜 : 2023.03.19

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.
DP의 꽃 냅색 문제이다.

2. 사고과정

지난 번에 한 번 풀었었던 문제를 다시 푸는데 쉽게 풀리지 않았다.
다시 푸는 문제임에도 못 풀어서 풀이를 참고했다

3. 풀이과정

1. 현재 무게에서 가방 i 번째 무게를 추가할 수 있다면
   dp값을 갱신
2. 추가할 수 없다면 이전의 가방값과 동일

4. 소스코드

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

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;


		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int K=Integer.parseInt(st.nextToken());
		int bag[][]=new int[N+1][2];
		for(int i=1;i<bag.length;i++) {
			st=new StringTokenizer(br.readLine());
			bag[i][0]=Integer.parseInt(st.nextToken());
			bag[i][1]=Integer.parseInt(st.nextToken());
		}

		int dp[][]=new int[N+1][K+1];

		for(int i=1;i<=N;i++) {
			for(int j=1;j<=K;j++) {
				int weight=bag[i][0];
				int cost=bag[i][1];
				if(j-weight>=0)
					dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight]+cost);
				else
					dp[i][j]=dp[i-1][j];
			}
		}

		System.out.println(dp[N][K]);


	}
}

5. 결과

5일만에 다시 푸는데 못풀었다 ㅠㅠ

6. 회고

그래도 지난 번 보다는 이 문제에 조금 더 접근했다.
그래서 다음 번에 다시 풀어볼 예정이다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212