문제 개요
오늘의 코딩 테스트 문제는 '평범한 배낭' 문제다. 백준 12865번.
문제 분석
•
N개의 물건 중 최대 무게 K를 넘지 않게 선택
•
각 물건의 무게 W와 가치 V가 주어짐
•
목표: 선택한 물건들의 가치 합의 최댓값 구하기
핵심은 주어진 무게 제한 내에서 가치를 최대화하는 것. 전형적인 DP 문제다.
접근 방식
1.
DP 배열 사용: dp[i][w]는 i번째 물건까지 고려했을 때, 무게 w에서의 최대 가치
2.
각 물건에 대해 선택 또는 미선택 결정
3.
점화식:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
구현
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int N, K;
cin >> N >> K;
vector<pair<int,int>> items(N, {0,0}); // 무게, 가치
for (int i = 0; i < N; i++)
cin >> items[i].first >> items[i].second;
vector<vector<int>> dp(N+1, vector<int>(K+1, 0));
for (int i = 1; i <= N; i++)
{
for (int w = 0; w <= K; w++)
{
if (w>=items[i-1].first)
dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i-1].first] + items[i-1].second);
else
dp[i][w] = dp[i-1][w];
}
}
cout << dp[N][K] << endl;
return 0;
}
C++
복사
주요 로직:
1.
물건 정보 입력 받기
2.
DP 배열 초기화
3.
각 물건에 대해 모든 무게를 순회하며 DP 배열 갱신
4.
최종 결과 출력
최적화
처음에는 1차원 DP로 접근했다가 실패. 2차원 DP로 변경하여 해결.
시간 복잡도: O(NK), 공간 복잡도: O(NK)
회고
1.
DP 문제인 건 바로 알았지만, 구현에 시간이 많이 걸렸다. 기본적인 DP 문제 패턴을 더 연습해야 할 것 같다.
2.
1차원 DP와 2차원 DP의 차이점을 명확히 이해하고 적용하는 능력이 필요하다.
3.
코드의 가독성과 효율성 사이의 균형을 잡는 연습이 더 필요하다.
이번 문제로 DP의 기본을 다시 한번 복습했다. 하지만 아직 부족한 점이 많다. 꾸준히 연습해 나가자.
