[백준] 12865번 : 평범한 배낭 [C/C++]

#문제

12865번: 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

---

#접근방법

모든 경우의 수를 따져야 하는 문제이다. 하지만 단순하게 백트래킹으로 접근하면 시간초과가 걸린다. 준서가 버틸 수 있는 무게가 100,000으로 제한이 되어있는 것에 초점을 두고 동적계획법으로 접근하면 된다.

반응형

---

#풀이

#include <stdio.h>
#include <algorithm>
using namespace std;

int dp[100005];

int main(){
	int n,k,w,v;
	
	scanf("%d %d",&n,&k);
	
	for(int i=0;i<n;i++){
		scanf("%d %d",&w,&v);
		
		for(int j=k;j>=w;j--)
			dp[j] = max(dp[j-w]+v,dp[j]);
	}
	
	printf("%d",dp[k]);
	
	return 0;
}

 

위에서 설명한 것 처럼 무게가 100,000이 최대라는 제한이 있다. dp배열의 크기를 넉넉하게 100,005까지 메모리를 할당해주고 배열의 인덱스는 무게, 내용물은 해당 무게일 때 가치의 최대값이라고 정의하겠다.

 

n과 k를 입력받고 반복문을 n번 돌려서 물건의 무게 w와 물건의 가치 v를 입력받는다.

 

그리고 w ~ k까지 반복문을 돌려서 dp[j]에 dp[j-w]+v, dp[j] 둘 중에 큰 값을 넣는다. dp[j-w]+v는 해당 무게 j에서 w를 뺀 값에서 해당 물건을 배낭에 넣었을 때, 이때까지 넣었던 물건의 가치보다 더 가치가 높은지 확인하는 것이다.

 

w ~ k까지 반복문을 돌릴 때, 주의 할 점이 있다. j++로 돌리면 해당 물건이 1개가 아닌 여러개가 들어간다는 것이다. 따라서 k부터 w로 역순으로 돌려야 해당 물건 1개만 들어가게 된다.

 

마지막 항 dp[k]를 출력하면 배낭에 넣을 수 있는 물건의 가치가 최대값이 되므로 정답이다.

---

#성능

---

#정리

물건의 무게에 초점을 두어서 동적계획법을 생각하는 것,

 

반복문을 역순으로 돌리면 풀 수 있는 문제였다.