[백준] 12865 : 평범한 배낭

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

DP를 이용하여 Top-down 방식으로 해결해보았다.

 

f(i, kg)는 i번째 물건을 넣을지 말지 판별 시에, 현재 배낭에 kg만큼 무게가 차있을 때의 최대 가치값을 리턴하는 함수이다.

 

처음에는 최초 함수 호출을 f(0, 0) 호출 대신 f(N-1,K) 호출로 생각하여 Base 조건을 찾는게 까다롭게 느껴졌으나,

f(0, 0)로 첫 함수 호출을 하여 i가 N 이상일 때, kg가 K 초과 시 0을 리턴하며 함수 호출이 끝나도록 조건을 거꾸로 생각하니 처음보다 수월하게 구현되었다.

 

아직 dp배열을 유지하는 레퍼런스 타입 변수 ret의 사용이 익숙치 않아서 DP 문제를 해결하며 숙련도를 높여야 한다.

#include<iostream>
#include<string.h>

using namespace std;

int w[101], v[101];
int dp[101][100001];
int N, K;

int f(int i, int kg) {
	if (i >= N || kg > K) return 0;
	int& ret = dp[i][kg];
	if (ret != -1) return ret;
	if (K - kg >= w[i]) {
		ret = max(f(i + 1, kg), f(i + 1, kg + w[i]) + v[i]);
	}
	else {
		ret = f(i + 1, kg);
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> K;
	memset(dp, -1, sizeof(dp));

	for (int i = 0; i < N; i++) {
		int iptW, iptV;
		cin >> iptW >> iptV;
		w[i] = iptW;
		v[i] = iptV;
	}
	cout << f(0, 0);

	return 0;
}