데옴's 기록장

이번에도 그리디로 돌아왔다. 아마도 내 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를 선택하는 것이다. 문제에서 말했듯 이미 회사..

역시 우사코 문제는 정말 좋은 것 같다. 그리디 문제가 다 그렇듯(?) 아이디어 떠올리는 것은 좀 힘들었다. 체감 티어: P2 태그: greedy, sorting 우선 한번 단순하게 생각해 보자. 일단 올라가는 속도가 빠른 소부터 보낸다고 생각한다면 아주 틀린 것은 아니다. 하지만 만약 내려가는 소가 있지만 올라오는 소의 속도가 더 느리다면 내려가는 소가 다 내려간 후 공백이 생긴다. 이 내용을 토대로 생각해 보자, 올라오는 소와 관계없이 내려가는 소가 계속 존재한다면 시간 이득을 볼 수 있다. 이미 올라간 소가 내려올 때 올라오는 소의 속도가 더 느리면 결국엔 이 구간에서 총 걸리는 시간은 올라오는 소의 것이 된다. 결국 이 말은 내려오는 소의 속도가 느린 만큼 더 많은 소가 올라와서 정상에 대기할 수..

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