(백준 12865번 평범한 배낭 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 7

오늘은 배낭 문제를 풀어보았다. 회사갈 때 재미로 코딩테스트 푸는 영상을 보는데, 문제를 읽다보니 어제 본 문제랑 똑같았다!!!!

 

아래 유튜브 아니였으면 평생 못 풀고 이해도 못했을텐데..😖 영상이 진짜 잘 설명해준다!!!!(강추)

 

https://www.youtube.com/watch?v=rhda6lR5kyQ

 

백준 12865번

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

12865번: 평범한 배낭

 

풀이의 방향을 영상을 보고 알고 있었음에도 2시간 반이나 걸렸다. 

DP를 풀면서 계속 실수하는 부분인데, input을 받아서 DP배열에서 찾을 때 배열이 0부터 시작한다는 사실을 자꾸 까먹는다.

 

#define  _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 102, MAX_K = 100002;
int N, K, W_V[MAX_N][2], DP[MAX_N][MAX_K];

long long f(int n, int k) {
	if (DP[n][k] != -1) return DP[n][k];

	long long result = f(n-1, k);
	if (k >= W_V[n - 1][0]) result = max(f(n-1, k - W_V[n - 1][0]) + W_V[n - 1][1], result);
	DP[n][k] = result;
	return result;
}
int main() {
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) scanf("%d %d", &W_V[i][0], &W_V[i][1]);
	if (N == 1) {
		int result = W_V[0][0] > K ? 0 : W_V[0][1];
		printf("%d", result);
		return 0;
	}
	
	for (int i = 0; i < N + 1; i++) fill_n(DP[i], K+1, -1);
	for (int i = 0; i < N + 1; i++) DP[i][0] = 0;
	for (int j = 0; j < K + 1; j++) DP[0][j] = 0;
	printf("%lld", f(N, K));
	return 0;
}

 

주요 실수 내용

1. return 원하는 값을 하는 것은 프린트를 하는게 아니다!!!

이 부분  때문에  컴파일 에러(NZEC)가 났는데.. 99%에서 에러가 나서 찾는데 고생 좀 했다..

2. DP 배열의 크기는 N * K 가 아닌 (N+1) * (K+1)이다.

3. 값을 계산한 다음에는 꼭 DP에 업데이트해야한다     

 

ㅎㅎ...

그래도 오늘도 한 문제 풀었다!!!!!!

 

햅삐-!