[C++] 백준(BOJ) - 1480 : 보석 모으기
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
세준이는 잘 모르겠지만, 세준이는 보석에 미쳐있다. 따라서, 숌 보석상에 있는 모든 보석을 다 훔치려고 한다. 하지만, 세준이는 보석을 다 가져올 수는 없다. 그 이유는 가방의 개수에 제한이 있고, 한 가방마다 넣을 수 있는 보석의 개수가 제한이 있기 때문이다. 세준이는 M개의 가방을 가지고 있다. 그리고 각각의 가방은 C그램의 보석을 담을 수 있다.
숌 보석상에는 보석이 N개 있다. N개의 보석의 무게가 주어졌을 때, 세준이가 훔칠 수 있는 보석의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C가 주어진다. N은 1보다 크거나 같고, 13보다 작거나 같은 자연수이고, M은 1보다 크거나 같고, 10보다 작거나 같은 자연수이다. C는 1보다 크고, 20보다 작거나 같은 자연수이다. 둘째 줄에 보석의 무게가 하나씩 주어진다. 보석의 무게는 1보다 크거나 같고, 20보다 작거나 같은 자연수이다.
출력
첫째 줄에 세준이가 가져갈 수 있는 최대 보석의 개수를 출력한다.
알고리즘
- DP
풀이
- 상태값 정의
- dp[현재가방][보석][최대용량]
- 현재 가방에서 다음 가방으로 넘어갈 시 최대 capacity는 c로 다시 초기화 필요
- 보석은 $2^{13}$ 의 경우의 수를 가짐 => 비트마스킹 int 형으로 처리 가능
코드
// BOJ - 1480 : 보석 모으기
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int n, m, c, w, a[14], dp[14][1 << 14][21];
int go(int idx, int jewel, int capacity)
{
if (idx == m) return 0;
int& res = dp[idx][jewel][capacity];
if (res) return res;
for (int i = 0; i < n; i++)
{
if (jewel & (1 << i)) continue; // 이미 jewel을 담은 상태면 continue
if (capacity < a[i])
{
res = max(res, go(idx + 1, jewel, c)); // 가방 용량보다 넣을 보석의 크기가 클 때 (보석 넣기 불가)
}
else
{
res = max(res, go(idx, jewel | (1 << i), capacity - a[i]) + 1); // 보석 넣기 가능할 때
}
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> c;
for (int i = 0; i < n; i++) cin >> a[i];
cout << go(0, 0, c) << '\n';
return 0;
}
평가
- 브루트포스 완전탐색으로 진행해보기
- (13개 중에 1개 뽑기, 2개뽑기, 3개뽑기) * 12개 중에 1개 뽑기, 2개뽑기, … , ) * …
- 너무 많은 경우의 수
- DP 배열에 저장하기
- Optimal Substructure : 최적 부분구조
- Overlapping subproblems : 겹치는 부분의 문제가 존재
- 참조 투명성
