솔직히 이 문제는 못 풀었다 풀이를 보고나서 이해를 할 수 있었다 이 문제의 코드는 그리 길지 않지만 하나의 로직을 아는사람이 풀 수 있었다. 핵심로직은 내가 어떠한 무게추를 들고 있다고 가정하자 일단 1이라는 무게추가 있다고 가정 하자 1이라는 무게추가 있을 때 다음 무게추가 지금 내가 가지고 있는 무게추의 무게보다 크게 되면 사이 무게인 2를 만들 수없다.
다른 예시로 현재 내가 1,1,2 이렇게 총 3개의 무게추를 가지고 있는데 다음 무게추로 6이 들어오게 되면 나는 4를 만들 수 없다
즉 현재 내가 가지고 있는 총 무게추의 무게보다 작은 무게들을 다 만들 수 있을 때 다음에 사용할 무게추는 내가 가지고 있던 총 무게보다 작아야 한다.
해당 로직이 이문제를 풀 수 있게 하는 핵심 로직이었다
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int arr[1000];
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
sort(arr, arr + N);
int res = 1;
for (int i = 0; i < N; i++) {
if (arr[i] > res) {
break;
}
res += arr[i];
}
cout << res;
}
이 문제의 경우 그리디와 비트 마스킹 문제이다 처음에는 while문으로 코드를 작성했으나 해당 문제를 해결 하려했으나 실패 했다. 이에 비트 마스킹을 사용해서 문제를 풀어야 함을 깨달았다. 이 문제를 풀기 위한 생각은
3리터짜리 물병을 생각해 보면 2리터 물병 하나 1리터 물병이 있다고 가정 하자. 얘를 물병 한개짜리를 만드는 방법은 1리터짜리 물병을 하나더해서 2리터짜리를 만든후 4리터 물병을 만드는 방법이다
즉 이문제를 풀기 위해서는 가장 작은 물병들을 계속 그다음 큰 물병들로 만들면서 진행 해야한다 자 대표적인 예로 2번째 테스트 케이스를 예시로 생각해봅시다
이 문제의 경우 0번째 칸에 있는 1리터짜리 물병을 일단 큰물병으로 만들어보자 1+1 해서 2리터로 만든다 그 후 최소 물병과 다른 물병의 갯수를 저장해놓고 일단 계속 가장 작은 물병을 다음 큰 물병으로 변경시켜 가면서 물병을 합치면서 크기를 늘리면서 갯수를 줄이는 로직이다 그후 최소 물병의 갯수를 만족하면 로직진행을 끝내면 된다
#include<bitset>
#include<iostream>
using namespace std;
int main() {
int n, k;
int ans=0;
cin >> n >> k;
while (true) {
int temp = n;
// 현재 1을 못만났다는 의미
int firstOnidx = -1;
// 내가 가지고 있는 물병의 갯수
int cnt=0;
// 내가 비교하려는 인덱스의 번호
int idx = 0;
//현재 물병의 수를 세는 로직
while (temp) {
if (temp & 1) {
if (firstOnidx == -1)
firstOnidx = idx;
cnt++;
}
idx++;
//다음 번째 인덱스를 비교하기 위해 오른쪽으로 1칸 이동
temp >>= 1;
}
//
if (cnt <= k) {
break;
}
else {
//가장 작은 양이 담겨져 있는 물병을 합쳐서 다음 크기의 물병을 만들기 위함 반복하다보면 원래있던 더큰 크기의 물병과 합쳐지면서 크기가 줄어듬
n += (1 << firstOnidx);
//산 물병의 갯수 크기2짜리 물병은 1개짜리 물병 2개 합친것
ans += (1 << firstOnidx);
}
}
cout << ans;
}
이 문제의 경우 그리디 문제이다 이 문제의 경우 Priority Queue로 풀면 쉽게 풀리는 문제였다. 일단 나는 이 문제를 보고 냅색문제 와 비슷 하다고 생각했다.
일단 나는 이문제의 숙제의 중요도를 숙제의 점수 라고 생각 했다 이에 우선순위 큐에 과제를 끝냈을 때의 점수가 가장 높은것들 순으로 나열 시켰다.
7
4 60
4 40
1 20
2 50
3 30
4 10
6 5
우리의 테스트 케이슬 중요도 즉 과제를 맞췄을 때의 점수를 해당로직대로 내림차순 정렬 하게 되면 아래 그림 처럼 된다
우리가 실제로 과제를 한다 생각 해 보자 우리는 당연히 가장 중요한걸 될 수 있는 한 최대한 미룰 것이다 즉 첫번째 4,60은 아직 4일 차에 내가 할 일이 없으므로 60에 중요도를 가진 과제를 한다.
그후 오는 2,50은 아직 2일차에 아무일도 없으므로 50에 일을 한다
그 후 4,40의 일은 4일 안에만 하면 되나 4일차에는 60의 일이 있으므로 4일보다 앞에 배정한다 그래서 3일 차에 40의 일을 한다
그후 3,30은 이미 3일차에 40의 일을 하였으니 3일안에 내가 할수 있는 요일은 1일차 밖에 없다 이에 30의 일은 1일 차에 한다
그후 1,20의 일은 이미 1일차에 30의 일을 하니 하지 않는다
그후 4,10의 일도 이미 4일 안에 진행 하는 일들은 다 중요도 가 높으므로 진행 하지않는다 그후 6,5는 6일차는 비어 있으므로 넣는다
즉 이문제의 풀이는 날짜를 최대한 미루데 중요한거를 우선 해서 리스트에 넣어야 한다 이에 만약 내가 4,40의 일을 한다고 가정했을 때 지금 업무를 완료했을 때의점수순으로 나열했기에 후에 나보다 낮은 일수가 나온다고 해도 점수가 높지 않고 일수도 낮고 점수도 낮은게 나올 수가 없으므로 빈공간에 채워주는 식으로 로직을 진행해야 한다
#include<iostream>
#include<queue>
using namespace std;
int day[1001] = {};
struct Compare {
bool operator()(pair<int, int> const& p1, pair<int, int> const& p2) {
return p1.second < p2.second;
}
};
priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pq;
int main() {
int N;
cin >> N;
int num1, num2;
int maxIdx=0;
int result = 0;
for (int i = 0; i < N; i++) {
cin >> num1 >> num2;
if (num1 > maxIdx) {
maxIdx = num1;
}
pq.push({ num1,num2 });
}
while (!pq.empty()) {
int x, y;
x = pq.top().first;
y = pq.top().second;
pq.pop();
if (day[x]== 0) {
day[x] = y;
}
else {
for (int i = x - 1; i > 0; i--) {
if (day[i] == 0) {
day[i] = y;
break;
}
}
}
}
for (int i = maxIdx; i > 0; i--) {
result += day[i];
}
cout << result;
}
