백준 12865 _ 평범한 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

---

✨ 내 소스 코드

#include<iostream>
#include <string>
#include<algorithm>
using namespace std;
int N, K, dp[101][100001], W[101], V[101];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N, K;
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> W[i] >> V[i];
	}

	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			if (i == 0) {
				if (j - W[i] >= 0) {
					dp[i][j] = V[i];
				}
			}
			else {
				dp[i][j] = dp[i - 1][j];
				if (j - W[i] >= 0) {
					dp[i][j] = max(dp[i][j], dp[i - 1][j - W[i]] + V[i]);
				}
			}
			
		}
	}
    
	cout << dp[N][K] << endl;
	
	return 0;
}

 

🙏 문제 풀이

dp배열은 dp[물건][무게] = 값어치 를 의미한다

백준의 예제 입력으로 위 코드의 DP 배열을 살펴보면

다음과 같은 DP 배열이 만들어져서 결과인 dp[N][K] 값으로는 14가 출력되게 된다

 

 

하나씩 자세히 살펴보면, 일단 1번 물건만 가지고 있을 때를 살펴보자 (dp[0])

물건이 1개 밖에 없기 때문에 확인 할 건, 현재 무게에 해당 물건을 넣을 수 있느냐 없느냐 뿐이다

물건을 넣을 수 없으면 그대로 0, 넣을 수 있으면 해당 물건의 무게를 넣어준다 

 

 

1번, 2번 2개의 물건을 가지고 있을 때를 살펴보자 (dp[1])

현재 물건을 넣지 않는 않았을 때의 값어치와, 현재 물건을 넣었을 때의 값어치를 비교하여 더 큰 값을 취하게 된다

 

dp[1][6]같은 경우, dp[0][6] = 13과 dp[0][2]+8 = 8 을 비교하게 된다 8과 13중 13이라는 값이 더 크기때문에 dp에 저장

 

 

1번, 2번, 3번 3개의 물건을 가지고 있을 때를 살펴보자(dp[2])

dp[2][4]의 경우, dp[1][4] = 8 과 dp[1][1] + 6 = 6을 비교하게 된다. 둘 중 큰 값을 취해서 dp에 저장

나머지의 경우도 위와 같이 진행되게 된다

 

 

⭐ 문제 풀이 결과