hades

🥅 문제https://www.acmicpc.net/problem/1138 🔍 설계큰 것을 먼저 배치하면, 선택의 폭이 많기 때문에 좋지 않다. 작은 것, 즉 앞에 있는 것부터 배치한다. 작은 것부터 배치하기 때문에 반복문으로 순회하면서 큰 것이 있는 상황은 고려하지 않아도 된다. 순회하는 과정에서 채워지지 않아서 0이라면, 자신보다 큰 사람의 수에서 1을 뺀다. 계속해서 빼다가 -1이 되면 배치한다. 👊 풀이 #include #include #include using namespace std;int n, smaller;vector v(10);int main(void){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i ..

🥅 문제https://www.acmicpc.net/problem/1202 🔍 설계가방에는 가방이 담을 수 있는 무게 이하의 보석만 담을 수 있다. 보석을 어떻게 담을지가 문제다. 보석과 가방의 무게를 오름차순으로 정렬하고, 가방마다 담을 수 있는 보석 중 최대 가치를 결과에 더하면 된다.  최대 가치는 우선순위 큐를 이용하여 구한다. 탐색하는 보석에 대하여 인덱스를 공유하면, O(N+K)로 해결할 수 있고, 우선순위 큐를 공유함으로써 그 가방 최대 무게 이하의 보석을 고려할 수 있다. 👊 풀이#include #include #include #include using namespace std;int n, k, m, v, c, p = 0;long long result = 0;vector> jewel;v..

🥅 문제https://www.acmicpc.net/problem/30805 🔍 설계사전 순으롤 가장 뒤에 있는 공통 부분 수열을 찾으면 되므로, 먼저 각 수열을 큰 수가 앞에 오도록, 수의 크기가 같다면, 인덱스가 작은 것이 앞에 오도록 하게 하기 위해 우선순위 큐를 이용하였다.  각각의 우선순위 큐에서 앞에 있는 하나를 꺼내면서 같다면, 결과에 추가한다.다르다면, 큰 것이 있는 우선순위 큐에서 하나를 없앤다. 큰 것이 계속 남아있다면, 그와 같은 것이 다른 쪽에 없기 때문이다. 주의해야할 것은 크기 뿐만 아니라 결과에 포함되는 수가 각각 양쪽 수열에서 어느 인덱스에 위치하는 지를 기록하고, 그 인덱스보다 작다면 결과에 추가될 수 없으므로 없애는 과정이 포함되어야 한다. 👊 풀이#include #i..

🥅 문제https://www.acmicpc.net/problem/11501 🔍 설계어느 날의 가격보다 이후의 날 가격들 중 가장 높을 때 팔아야 이익을 최대화할 수 있다. 가장 가격이 높은 날에 팔고, 그 날 이후의 날들 중에서 가장 가격이 높은 날 팔고, 이 방식을 반복해야 한다. 현재 상황에서 가장 높은 가격을 구하기 위해 우선순위 큐를 활용했는데, 중요한 것은 남아있는 가격들 중 가장 높은 가격에 차익을 보고 판매한 주식 가격들이 있으므로, 인덱스를 함께 담아 제거해야 한다. 맨 뒤까지 고려했을 때, 주식 가격이 가장 높은 지점에서 팔아야 한다. 순서를 바꿔서 맨 뒤부터 최댓값을 갱신하면서 차이를 빼주면 간단하게 해결할 수 있다. 👊 풀이#include #include #include #inc..

🥅 문제https://www.acmicpc.net/problem/11399 🔍 설계인출하는데 시간을 많이 쓰는 사람이 앞에 오면, 뒤에 사람들이 기다려야 하는 시간이 그만큼 늘어나므로, 인출 시간을 기준으로 오름차순으로 정렬한다. 어떤 사람이 인출하는데까지 걸리는 시간은 앞 사람들이 인출하는데 걸리는 시간 + 본인이 인출하는데 걸리는 시간이다. 👊 풀이#include #include #include using namespace std;int n;vector p;int main(void){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; p = vector(n); for (int i = 0; i > p[i]; } sort(p.begin(..

🥅 문제https://www.acmicpc.net/problem/1931 🔍 설계회의실 하나에 최대로 몇 개의 회의가 가능한지 구해야 한다. 회의의 시작 시각이 빠른 것을 먼저 고려하기 위해서 첫 번째로 회의의 시작 시각, 두 번째로 회의의 종료 시각을 기준으로 하여 오름차순으로 값을 꺼낼 수 있는 우선순위 큐를 만들었다. 고려해야할 것은 (시작 시각, 종료 시각)이라고 할 때, (0, 6) 대신 (1, 3) (3, 6)이 결과값을 도출하는 회의의 개수에 포함된다. 시작 시각이 가장 빠른 회의의 시작 시각이 다음 회의가 시작 가능한 시각(next_available_time) 보다 뒤라면, 할 수 있는 회의가 한 개 증가한다. 그리고, next_available_time을 그 회의의 종료 시각으로 갱신..

🥅 문제https://www.acmicpc.net/problem/1541 🔍 분석괄호를 쳐서 식의 값을 최소로 해야 하는데, 최소로 하는 방법은 - 뒤에 있는 값은 괄호로 묶어주면 된다. - 뒤에 -가 나온다면 -(A+B)-(C+D)처럼 생각하면 된다. 즉, -가 한 번이라도 나오면 뒤에 있는 수들은 빼기만 하면 된다.  식의 마지막 수를 처리하기 위해 기호를 추가하는 방식을 사용했다.  👊 풀이#include #include #include #include using namespace std; string str, temp = "";bool minus_appeared = false;int result = 0;int main() { cin.tie(NULL); ios_base::sync_with_st..

🥅 문제https://www.acmicpc.net/problem/11047 🔍 설계K를 달성시키는 동전의 최소 개수를 구해야 하는데, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수라는 조건이 있으므로, 가치가 큰 동전부터 최대한 사용하는 그리디 문제라는 것을 파악할 수 있다. 👊 풀이#include #include #include #include using namespace std;int n, k, result = 0;vector coins(10);int main() { cin >> n >> k; for (int i=0; i> coins[i]; } for (int i=n-1; i>=0; i--){ result += k / coins[i]; k %= coins[i]; } cout