데옴's 기록장

아이디어만 있다면 풀 수 있다 이건가요? 내가 문제 2개를 고르면 상대가 가장 자신 있는 문제 하나를 가져간 후 내가 남은 문제를 가져간다.'나'와 상대는 i 번째 문제에 대해 각각 Ai, Bi 만큼의 자신감 수치를 가지고 있다.내가 문제 2개를 고르지만 정작 문제의 선택권은 상대에게 있다.문제 2개를 적절하게 잘 고르면 최적의 상황을 얻을 수 있다는데.... 당장은 보이지 않는다.우선 문제의 선택권이 상대에게 있다는 것에 초점을 두고 Bi를 기준으로 정렬을 해보자.4 2 8 66 5 7 8  2 4 8 65 6 7 8 여기서 맨 뒤에 있는 문제는 무조건 상대가 가져가는 문제, 맨 앞의 문제는 무조건 내가 가져갈 수 있는 문제임을 알 수 있다.그럼 어떤 식으로 두 개의 문제를 골라야 자신감 수치를 최대화..

여행 갈 때 얼마나 효율적으로 돈을 사용할 수 있는지 생각을 해본 적은 따로 없던 것 같다.가끔 코딩 문제를 풀다 보면 이런 상황을 자주 마주치게 되는 거 같아 나름? 신선한 거 같기도 하고..아무튼 이번 문제는 티어에 맞는 난이도를 가지고 있는 것 같다.  문제 요약을 하자면 지내야 하는 호텔들의 수가 주어진다.각 호텔마다 Pi만큼의 돈을 내야한다.호텔에 한번 숙박하면 1개의 쿠폰을 주고 k 개의 쿠폰이 모이면 호텔을 한번 무료로 숙박할 수 있다.이때 사용해야 하는 최소 금액을 출력하는것이 문제가 원하는 것이다. 당연히 호텔에 숙박할 때마다 쿠폰 개수가 k보다 크면 사용하는 것이 이득이다.문제는 이 쿠폰을 어떤 호텔에서 사용하는것이 관건인 것이다.호텔에 사용할 쿠폰을 정하는것은 최소 힙를 이용해 판별해..

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$라고 해보자, 다음 손님이 왔을 때 그 계산대에서 계산을 끝마치..

유명한 그리디의 스케줄링 문제이다. 발상이 떠오르지 않는다면 어려울 수 있는 그리디 문제이다. 그러나 한번 알아두면 평생 쓴다! 어떤 방법으로 강의들을 배정해야 최소한으로 필요한 강의실을 개수를 구할 수 있을까? 순서대로 계획을 짜보자 1. 빨리 시작하는 순으로 배정한다. 시작이 빠른 강의가 가장 늦게 끝나는 경우가 있음으로 사용하기 어렵다. 2. 강의 시간이 짧은 순서대로 배정한다. 강의 시간이 짧은 강의가 제일 나중에 나오게 되면 비효율적이다. 3. 적게 겹치는 강의부터 배정한다. 이 역시 쉽게 반례를 찾을 수 있다. 4. 빨리 끝나는 순으로 배정한다. 뭔 짓을 해도 반례를 찾을 수 없다. 전략이 나왔다. 빨리 끝나는 순으로 강의를 배정시켜 보자. 이는 우선순위큐를 이용해 배정할 수 있다. 빠른 순으..

체감 난이도: D5 태그: 그리디, 정렬, 우선순위 큐 문제 요약: 최소 개수의 강의실을 사용해 모든 강의를 진행하게 한다. (단 1번 강의와 2번 강의는 같은 강의실에 배정하면 안 된다.) 강의실 배정의 상위 버전 문제이다. 우선 평범하게 강의실 배정을 하는 로직을 기반으로 생각 해보자. 만약 가장 빨리 끝나는 강의실에 1번 또는 2번 강의가 있는데 2번 또는 1번 강의가 들어온다면 다음으로 빨리 끝나는 강의실에 배정하는 식으로 진행시켜보자. 아래와 같은 상황이 들어오면 어떨까? 더보기 7 1 2 6 8 1 2 2 4 3 5 4 6 5 7 강의실 배정을 조금 변형한 방법으로는 이 상황을 해결할 수 없다. 위 상황을 조금 보기 쉽게 정렬해보면 아래와 같다. 더보기 1 2 (1) 1 2 (3) 2 4 (4..

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

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

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