백준 12865 평범한 배낭

백준 12865 평범한 배낭

구현전 생각

DP를 이용해서 해당하는 물건들의 가치의합의 최댓값을 출력한다.

아쉬운 점

final 프로젝트 등 웹개발을 공부하다 보니까 알고리즘 문제를 거의 2주만에 풀고 있습니다. 그러다 보니 쉽게 풀었던것 같던 문제도 제대로 푸는데 오래 걸렸습니다.

먼저 DP를 떠올릴때 막혔던 생각

1. 넣은것과 안 넣은것을 어떻게 표현할지 생각 하지 못함.
   -> 2차원 배열로 해결 ( 1차원으로 해결하는 방법 존재 )

2. DP배열을 만들때 내가 가지고 있지 않은 무게를 어떻게 해결할까 -> 3번을 이용해서 채운다는 생각!

3. 순차적으로 들어오는 데이터를 바로바로 계산해야한다는 생각! -> 한번에 받아서 나중에 사용하는 방법으로 해결

2차원 배열 코드

package argorithm_study_june;

import java.util.Scanner;


public class backjoon_12865_평범한배낭 {

	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); //물건의 개수
		int k = sc.nextInt(); // 가방의 무게
		
		int weights[] = new int[N+1];
		int profits[] = new int[N+1];
		int bag[][]= new int[N+1][k+1];
		
		for (int i = 1; i <= N; i++) {
			weights[i]=sc.nextInt();
			profits[i]=sc.nextInt();
		}
		
		for (int i = 1; i <=N; i++) {
			for (int w = 1; w <=k; w++) {
				if(weights[i]<=w) {
					
					//가방에 넣을 수 있는 상황
					//넣을까
					bag[i][w]=Math.max(bag[i-1][w-weights[i]]+profits[i] , bag[i-1][w]);
					//말까
				}else { //가방에 넣지 못하는 상황
					bag[i][w]= bag[i-1][w];
				}
			}
		}
		System.out.println(bag[N][k]);
	}
	
}

1차원 배열 코드

package argorithm_study_june;

import java.util.Scanner;


public class backjoon_12865_평범한배낭2 {

	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); //물건의 개수
		int k = sc.nextInt(); // 가방의 무게
		int[] DP = new int[k+1];
		
		 for (int i = 0; i < N; i++) {
	            int W = sc.nextInt();
	            int V = sc.nextInt();
	            for (int j = k; j >= W; j--)
	                if (DP[j] < DP[j - W] + V) 
	                	DP[j] = DP[j - W] + V;
	        }

	        System.out.print(DP[k]);

	}
	
}