데옴's 기록장

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, 주식의..