이 문제는 전형 적인 그리디 문제이다 그리디 문제의 특징은 모든 과정에서의 답이아니기 때문에 풀 수 있다
이문제는 일단 주의 할점을 일반적으로 input을 받으면 int 형자료형은 50만자리의 수를 받을 수없기 때문에 string으로 input을 받아 사용하는게 좋다
또한 이문제는 스택을 두고 이전에 들어온 값들보다 현재 들어오는 값들을 뽑고 거기에 넣으면서 뽑은 횟수를 저장해야한다 그래서 만약에 최대 뽑기수보다 못뽑으면 그냥 그상태로 값이 나온다
#include<iostream>
#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
stack<long long> bigStack;
stack<long long> answerStack;
long long n, k;
string num;
vector<long long> arr;
long long popCount=0;
long long result = 0;
int main() {
cin >> n >> k;
cin >> num;
for (int i = 0; i < num.length(); ++i) {
arr.push_back(num[i] - '0'); // 문자 '0'을 빼서 실제 숫자로 변환
}
if(arr.size()!=0)
bigStack.push(arr[0]);
for (long long i = 1; i < n; i++) {
while (!bigStack.empty()&& bigStack.top() < arr[i] && popCount<k) {
bigStack.pop();
popCount += 1;
}
bigStack.push(arr[i]);
}
while (popCount < k) {
bigStack.pop();
popCount += 1;
}
while (!bigStack.empty()) {
answerStack.push(bigStack.top());
bigStack.pop();
}
while (!answerStack.empty()) {
cout << answerStack.top();
answerStack.pop();
}
}
이 문제의 경우 흐름대로 생각하면 그게 정답이다 단 주의 할점은 단지 하나의 priority queue로 만한다면 음수부분의 처리가 이상하게 될것이다 이에 나는 음수와 0을 저장하는 priority queue와 양수만을 저장해주는 priority queue로 작성하였으며 음수 와 0을 묶은 이유는 음수와 음수의 곱은 양수이고 만약 음수와 0만 큐에 남았을 때는 2개를 곱하여 0을 반환함으로 작은 값을 반환할거라고 생각했다
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> plusNum;
priority_queue<int,vector<int>, greater<int>> negativeNum;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int temp1;
cin >> temp1;
if (temp1 > 0) {
plusNum.push(temp1);
}
else {
negativeNum.push(temp1);
}
}
int sum = 0;
while (!plusNum.empty())
{
int num1, num2;
num1 = plusNum.top();
plusNum.pop();
if (plusNum.empty()) {
sum += num1;
break;
}
num2 = plusNum.top();
plusNum.pop();
if (num1 != 1 && num2 != 1) {
sum += num1 * num2;
}
else {
sum += num1 + num2;
}
}
while (!negativeNum.empty())
{
int num1, num2;
num1 = negativeNum.top();
negativeNum.pop();
if (negativeNum.empty()) {
sum += num1;
break;
}
num2 = negativeNum.top();
negativeNum.pop();
sum += num1 * num2;
}
cout << sum;
}
이 문제의 경우 Priority Queue를 사용하지 않으면 시간 초과 가 발생한다 이문제의 핵심은 작은 가방에 담을수 있는 가장 큰걸 담고 그다음크기의 가방에 그 가방의 크기에 담을 수 있는것중 가장 큰것을 담으면 된다. 이 로직을 구현하기 위해서는 일차적으로 가장 작은 무게에 담을 수 있는 모든 물건들을 선택한다 거기서 가장 큰 애를 선택한다. 이차적으로 이전에 담고 남은 물건들중에 두번째 무게에 담을 수 있는 모든 물건들을 모두 고른 후 이전 애 고른애들과 합쳐서 놓은 다음 그중에 큰거를 고르면 된다.
이 로직에서 일단 필요한건 우선순위 큐다. 일차적으로 가방을 작은 순으로 나열해서 가장 작은 가방에 담을 수 있는 애를 우선순위큐에 담는다 보석들도 무게순으로 정렬 되어 있다 그래서 첫번째 가방에 담으면 첫번째 가방에 담긴 마지막 인덱스 이후로 무게가 큰 보석들이 남는다 그중 두번째 가방에 닿을 수 있는 물건들을 담아서 우선순위 큐에 넣는다. 거기서 최고 큰값을 선택 한다
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
priority_queue<int> pq;
int bag[300000];
pair<int, int> jewerly[300000];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
int temp1, temp2;
cin >> temp1 >> temp2;
jewerly[i] = { temp1,temp2 };
}
for (int i = 0; i < k; i++) {
cin >> bag[i];
}
sort(jewerly, jewerly + n);
sort(bag, bag + k);
int idx=0;
long long sum = 0;
for (int i = 0; i < k; i++) {
while (idx < n && bag[i] >= jewerly[idx].first) {
pq.push(jewerly[idx].second);
idx++;
}
if (!pq.empty()) {
sum += pq.top();
pq.pop();
}
}
cout << sum;
}
솔직히 이 문제는 못 풀었다 풀이를 보고나서 이해를 할 수 있었다 이 문제의 코드는 그리 길지 않지만 하나의 로직을 아는사람이 풀 수 있었다. 핵심로직은 내가 어떠한 무게추를 들고 있다고 가정하자 일단 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;
}
이 문제의 경우 그리디 문제이다 이 문제의 경우 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;
}
이 문제의 경우 생각하는건 쉬웠다 사실 어떠한 배열에서 가장 작은 2개를 선택한 후 이를 그다음 작은애랑 더해주면 되는 문제였다 그래서 이문제를 나는 큐를 사용해서 풀고 싶었다. priority queue를 사용해서 풀고 싶었기 때문에 사실 데큐를 사용해서 풀수도 있는 문제기는 하다 데큐로 푸는 방식은 그냥 입력받은애들을 작은애들 순으로 소팅한 후 더한후 front에 넣고 다시 front에서 두개를 더한후 넣고 다시 두개 팝해서 넣고 하는 방식으로 하면 된다 이러한 로직도 priority queue에 적용이 되기 때문에 사용하면 된다 소스코드는 이렇게 된다
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
int main() {
int card;
int n;
int sum = 0;
cin >> card;
for (int i = 0; i < card; i++) {
cin >> n;
pq.push(n);
}
while (pq.size() > 1) {
int x, y;
x = pq.top();
pq.pop();
y = pq.top();
pq.pop();
sum += (x + y);
pq.push(x + y);
}
cout << sum;
}
이 문제의 경우 사실 dfs로푸는게 간단해보였다 하지만 문제 분류가 그리디로 되어있었으니 그리디로 풀어 보겠다
이문제의 경우 A와 B가 주어졌을 경우 A에서 B를 만든다고 생각하지말고 B에서 A로 가야한다고 생각해야 잘풀리는 문제였다 B가 일단 2로 나누어지는 경우 2로 나누고 B가 10으로 나누었을 때 1이 남으면 10으로 나눈다 그후 A와 비교해서 같으면 나오고 아니면 다시 실행한다 단 B가 A보다 작아졌을 경우는 문제의 답이 존재하지 않는 경우기 때문에 -1을
출력한다.
이문제의 경우 상당히 쉬웠지만 계속 A에서 B를 만들려고 하니 시간이 많이 소모되었다.
#include <iostream>
using namespace std;
int main() {
int A, B;
int countnum=0;
cin >> A >> B;
while (true) {
if (A == B) {
countnum += 1;
break;
}
if (A > B) {
countnum= -1;
break;
}
if (B % 10 == 1) {
B--;
B = B / 10;
countnum++;
}
else if (B % 2 == 0) {
B = B / 2;
countnum++;
}
else {
countnum= -1;
break;
}
}
cout << countnum;
}
