데옴's 기록장

k개의 소수들의 곱을 순서대로 나열할 때, n번째로 오는 숫자를 구하는 문제이다. 가장 단순하게 k개의 소수들로 만들 수 있는 숫자들을 만든다는 전략을 사용해 보자. i번째로 오는 수에 k개의 소수를 각각 곱하여 만들 수 있는 수를 우선순위큐에 넣어준다. 중복되는 경우가 있을 수 있기 때문에 하나의 경우만 있을 수 있도록 처리해 준다. 문제의 메모리가 적으므로 메모리 초과에 유의하자. 더보기 #define _CRT_SECURE_NO_WARNING #include #include #include #include using namespace std; using namespace __gnu_cxx; // utils #define fastio ios::sync_with_stdio(false);cin.tie(0)..

체감으로는 골드 4?정도로 느껴지는 우선순위큐를 잘 활용하는 법을 안다면 쉽게 구현할 수 있는 문제라고 생각한다. 문제를 꼼꼼히 읽으면 쉽게 접근법을 찾아낼 수 있다. 우선 요구사항을 정리하면 다음과 같다. 1. 계산대에 줄을 선 순서대로 고객이 들어온다. 2. 빨리 계산이 끝나는 계산대에 고객을 안내하고, 기다려야 하는 시간이 같다면 계산대 번호가 작은 순서대로 고객을 안내한다. 3. 계산이 끝나는 대로 고객이 나간다. 계산을 마친 고객이 여러 명이라면 계산대 번호가 큰 순서대로 나간다. 기본적으로 계산대에 사람이 있어야 하므로 처음 $min(k, n)$명에게 순서대로 계산대에 배정한다. 이제 계산이 가장 빨리 끝나는 계산대의 시간을 $t$라고 해보자, 다음 손님이 왔을 때 그 계산대에서 계산을 끝마치..

이번에도 그리디로 돌아왔다. 아마도 내 4번째 다이아 문제가 아닐까 한다... 지금까지 푼 다이아 문제 중 가장 어려웠던 것 같다. 가장 오랜 시간 고민하다가 결국 다른 방법을 찾아봐서 풀었던 기억이 난다. 체감 티어: D4 문제는 우리에게 단순한 것을 요구한다. 그저 k 개의 네트워크 케이블을 이용해 회사들을 연결하는데 가장 길이가 짧게 하는 것이다. 예제를 가지고 간단하게 살펴보자, 우선 0km부터 가장 가까운 회사부터 A, B, C, D, E라고 정의하겠다. A-B의 길이는 3-1=2km, B-C의 길이는 4-3=1km, C-D의 길이는 6-4=2km, D-E의 길이는 12-6=6km이다. 여기서 가장 길이가 짧게 가져갈 수 있는 방법은 A-B와 C-D를 선택하는 것이다. 문제에서 말했듯 이미 회사..

set 활용법을 몰라서 개고생한 문제.. 너무 힘들었다. 체감 티어 : G1 태그 : greedy, set 모든 행성을 효율적으로 정복하려면 어떻게 해야 할까? 일단 다음과 같은 행동을 취해볼 수 있다. 1. 인구수가 가장 작은 행성부터 정복해 mobilization을 한다. 2. 인구수가 많은 행성부터 정복해 mobilization을 한다. 1번 아이디어는 반례가 생긴다는 것을 몇번의 관찰로 알아낼 수 있다. 그럼 이제 2번 아이디어를 가지고 어떤 식으로 가져가야 할지 생각해 보자. 먼저 고려해야 할 것은 어떤 행성들에서 충원 할 것이냐이다. 이는 최소한의 횟수로 충원 해야 하기에 가장 중요한 부분이다. 일단 전체 행성들의 합들을 이용해 충원 할 행성들을 정해볼 수 있다. k 개의 우주선으로 정복할 수..

체감 티어:P3 태그:우선순위 큐, 정렬, 그리디 파머 존의 쿠폰을 뺏어가면 되는거 아닌가요 우선 파머 존에게 k 개의 쿠폰과 돈 m이 있다. 파머 존은 많은 소를 사고 싶어 하므로 최적의 방법으로 소를 살 수 있게 도와주면 된다. i 번째 소를 구입하려면 원가 Pi 또는 쿠폰 할인가 Ci를 지불해야 한다. 1. 쿠폰 할인가가 싼 소부터 쿠폰을 쓰는 것이 좋다 당연한 얘기이다. 하지만 원가를 지불하고 다른 소를 사는 것이 이득일 수 있다. 2. 쿠폰을 다른 소에게 쓰는 경우가 있을 수 있다 우리는 이것을 우선순위 큐를 통해 쿠폰을 쓸 필요가 없는 소를 찾을 수 있다! k 개의 쿠폰을 전부 사용해 쿠폰을 쓸 예정인 소 목록을 만들자. 이제 남은 소들을 보며 현재 Pi 원과 이전의 소를 쿠폰 없이 사고 Ci..

우연히 본 문제가 쉽게 관찰을 얻을 수 있어서 기분 좋게 구현을 해봤다. 결과는.. 참혹했다. 역시나 한번에 되지 않는 것인지 수많은 TLE가 나를 반겨주었다.. n log n 풀이가 안되는 줄 알았는데 그럴리가 없다고 생각해서 다시 구현해보니 그냥 구현미스였던거였..(나는 아무 생각이 없다ㅏㅏㅏㅏㅏㅏㅏㅏ) 그래도 많이 봤던 유형의 그리디가 섞여있는 문제여서 좋았(?)다 체감티어: G2 태그 : 그리디, 우선순위 큐 문제에서 3가지, i일에 얻는 주식의 양, 판매시 얻는 가치, i일에 팔 수 있는 최대 주식수가 주어진다. 일단 문제를 보자마자 알 수 있는 것은 주식을 '잘' 분배하는 문제라는 것이다. 분배방법은 우선순위 큐를 이용해 간단하게 판별할 수 있었다. 우선 i일에 얻는 주식의 양은 Xi, 주식의..