백준 12865. 평범한 배낭

🅰 백준 12865. 평범한 배낭

12865번: 평범한 배낭

✏️ 문제 풀이

• 먼저 버틸수 있는 무게 K만큼 반복하면서 현재의 물건이 가방에 넣을 수 있는지 확인해서 dp를 수행한다.
• product배열에 물품들의 무게, 가치를 저장해주고 dp배열은 N+1,kg+1로 생성해준다
• 2중 for문을 사용하면서 바깥 for문에는 물품의 수만큼 반복하고, 안쪽 for문에는 넣을수 있는 무게만큼(kg) 반복해준다
• 예제 입력 데이터 

     4 7

     6 13

     4 8

     3 6

     5 12 을 넣으면 오른쪽과 같은 테이블이 생성된다

 

 

✏️ 소스코드

package dp;

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

public class Main_골드5_12865_평범한배낭X {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int kg = Integer.parseInt(st.nextToken());

		int dp[][] = new int[N+1][kg+1];
		int product[][] = new int[N+1][2];
        
        // 데이터 입력
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			product[i][0] = Integer.parseInt(st.nextToken());
			product[i][1] = Integer.parseInt(st.nextToken());
		}

		// dp수행
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= kg; j++) {
				if (j - product[i][0] >= 0) {
				  dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-product[i][0]] + product[i][1]);
				}
				else {
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		System.out.println(dp[N][kg]);
	}
}

 

✅ 후기

• 가장 기본적인 dp문제인 knapsack문제이다. 더 다양한 dp문제를 풀면서 접근하는 방법에 대해 익숙해져야겠다