마을 축제의 밤샘 당번을 정한다. 밤은 1번부터 L번까지 L개의 시간 칸으로 나뉘어 있다. 지원자 n명이 저마다 설 수 있는 구간을 냈다. i번째 지원자는 sᵢ번 칸부터 eᵢ번 칸까지, 두 끝 칸을 모두 넣어 서겠다고 했다. 지원자를 뽑으면 그 사람은 자기가 낸 구간 전체를 선다. 구간의 일부만 세울 수는 없다. 모든 시간 칸에 뽑힌 사람이 k명 이상 서 있어야 한다. 같은 구간을 낸 지원자가 여럿 있어도 서로 다른 사람이라 따로 센다. 뽑아야 하는 사람 수의 최솟값을 출력하라. 지원자를 모두 뽑아도 k명이 안 되는 칸이 있다면, 그런 칸 가운데 번호가 가장 작은 칸을 출력하라.
입력
첫 줄에 지원자 수 n(1 ≤ n ≤ 10,000), 시간 칸 수 L(1 ≤ L ≤ 1,000,000,000), 칸마다 필요한 사람 수 k(1 ≤ k ≤ 5)가 빈칸 하나로 나뉘어 주어진다. 다음 n줄의 i번째 줄에 정수 sᵢ와 eᵢ(1 ≤ sᵢ ≤ eᵢ ≤ L)가 빈칸 하나로 나뉘어 주어진다. 지원자는 정해진 차례 없이 주어진다.
출력
모든 칸에 k명 이상 세울 수 있으면 뽑아야 하는 사람 수의 최솟값을 한 줄에 출력한다. 세울 수 없으면 -1과, 지원자를 모두 뽑아도 k명이 안 되는 칸 가운데 가장 작은 번호를 빈칸 하나로 띄워 한 줄에 출력한다. 숫자는 쉼표 없이 출력한다.
예시 1 · stdin
6 10 2
1 4
1 6
3 10
5 8
2 3
7 10
stdout
4
예시 2 · stdin
4 8 2
1 5
1 3
4 8
7 8
stdout
-1 6
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
탐욕법 문제예요. 아직 k명이 차지 않은 가장 앞 칸 x를 보면, 그 칸을 지킬 수 있는 사람은 x번 칸이나 그 앞 칸에서 시작하는 사람뿐이에요. 그 가운데 누구를 뽑아도 x 앞쪽은 이미 다 찼으니, 가장 늦게까지 서는 사람을 뽑는 것이 언제나 손해가 없어요. 그래서 지원자를 시작 칸 순서로 정렬하고, 시작 칸이 x 이하인 사람의 끝 칸을 최대 힙에 넣어요. x에서 모자란 수만큼 힙에서 꺼내 뽑아요. 뽑힌 사람 가운데 가장 먼저 끝나는 사람이 빠지기 전까지는 k명이 그대로이니, x를 그 끝 칸 + 1로 건너뛰어요. L이 10억이라 칸을 하나씩 볼 수는 없어요. 첫째 예에서 x = 1일 때 후보는 (1, 4)와 (1, 6)이라 둘 다 뽑아요. 먼저 끝나는 쪽이 4이니 x = 5가 돼요. 5번 칸에는 6에서 끝나는 사람만 남아 한 명이 모자라고, 후보 (3, 10), (5, 8), (2, 3) 가운데 가장 늦게 끝나는 (3, 10)을 뽑아요. x = 7에서 다시 한 명이 모자라 (7, 10)을 뽑으면 끝까지 두 명이라 답은 4예요. 둘째 예는 6번 칸을 지킬 수 있는 사람이 (4, 8) 한 명뿐이라 -1 6이에요. 힙 맨 위의 끝 칸이 x보다 작으면 x를 지킬 사람이 더 없다는 뜻이에요. 함정 하나: 먼저 시작한 사람부터 뽑으면 안 돼요. 첫째 예의 5번 칸에서 (2, 3)이나 (5, 8)을 고르면 사람이 더 들어요. 함정 둘: 힙 맨 위를 보기만 하고 꺼내지 않으면 한 사람을 여러 번 세요. 한 사람은 한 번만 뽑을 수 있어요. 함정 셋: 한 겹만 덮는 흔한 풀이(가장 멀리 닿는 구간 하나만 기억하는 방법)는 k가 2 이상이면 틀려요. 버린 후보를 나중에 다시 써야 하니 힙에 남겨 두어야 해요. 함정 넷: 다음에 볼 칸은 뽑힌 사람 가운데 가장 먼저 끝나는 칸의 다음이에요. 가장 늦게 끝나는 칸으로 건너뛰면 그 사이에 모자란 칸을 놓쳐요. 함정 다섯: 끝 칸도 지키는 칸이에요. 끝 칸이 x와 같은 사람을 이미 끝난 사람으로 치면 사람을 더 뽑게 돼요. 함정 여섯: 입력은 시작 순서가 아니에요. 정렬하지 않으면 뒤에 적힌 이른 지원자를 놓쳐요. 최대 힙은 언어마다 달라요. C++의 priority_queue는 처음부터 최대 힙이에요. Python의 heapq는 최소 힙뿐이라 부호를 바꿔 넣고, Java의 PriorityQueue는 Comparator.reverseOrder()를 줘요. C#의 PriorityQueue<TElement, TPriority>는 우선순위가 작은 것부터 꺼내니 우선순위에 -끝 칸을 넣어요. JavaScript, TypeScript, C, 크레이콘에는 힙이 없어서 배열(목록)로 직접 만들어요. 크레이콘은 넣기와 자리빼기로 목록 끝을 늘리고 줄여요. 정렬도 조심해요. JavaScript의 sort()는 비교 함수가 없으면 문자열로 견주어 10이 9보다 앞에 와요. C의 qsort 비교 함수는 (x > y) - (x < y)처럼 써요. 크레이콘은 정렬(비교함수)에 번호 목록을 넘겨 시작 칸으로 견줘요.
Pythonmain.py · 34 줄
import heapqimport sysdata = sys.stdin.buffer.read().split()n, length, k = int(data[0]), int(data[1]), int(data[2])shifts = sorted((int(data[3 + 2 * i]), int(data[4 + 2 * i])) for i in range(n))cand = [] # 아직 뽑지 않았고 x칸 이전에 시작하는 사람들의 끝 칸(최대 힙: 부호를 바꿔 넣는다)active = [] # 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개)nxt = 0 # 아직 후보에 넣지 않은 첫 사람chosen = 0x = 1 # 아직 k명이 채워지지 않은 가장 앞 칸fail = 0while x <= length: while nxt < n and shifts[nxt][0] <= x: heapq.heappush(cand, -shifts[nxt][1]) nxt += 1 active = [e for e in active if e >= x] # 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while len(active) < k: if not cand or -cand[0] < x: fail = x break active.append(-heapq.heappop(cand)) chosen += 1 if fail: break # 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 x = min(active) + 1if fail: print(-1, fail)else: print(chosen)
JavaScriptmain.js · 60 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const shifts = [];for (let i = 0; i < n; i++) shifts.push([data[3 + 2 * i], data[4 + 2 * i]]);shifts.sort((a, b) => a[0] - b[0]); // 비교 함수가 없으면 문자열로 견주어 10이 9보다 앞에 온다// JavaScript에는 힙이 없어서 배열로 최대 힙을 만든다. i의 자식은 2i+1, 2i+2function heapPush(heap, x) { heap.push(x); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (heap[parent] >= heap[i]) break; [heap[parent], heap[i]] = [heap[i], heap[parent]]; i = parent; }}function heapPop(heap) { const top = heap[0]; const last = heap.pop(); if (heap.length > 0) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let big = i; if (l < heap.length && heap[l] > heap[big]) big = l; if (r < heap.length && heap[r] > heap[big]) big = r; if (big === i) break; [heap[big], heap[i]] = [heap[i], heap[big]]; i = big; } } return top;}const cand = []; // 아직 뽑지 않았고 x칸 이전에 시작하는 사람들의 끝 칸(최대 힙)let active = []; // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개)let next = 0; // 아직 후보에 넣지 않은 첫 사람let chosen = 0;let x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸let fail = 0;while (x <= length && fail === 0) { while (next < n && shifts[next][0] <= x) heapPush(cand, shifts[next++][1]); active = active.filter((e) => e >= x); // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while (active.length < k) { if (cand.length === 0 || cand[0] < x) { fail = x; break; } active.push(heapPop(cand)); chosen++; } // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 if (fail === 0) x = Math.min(...active) + 1;}console.log(fail > 0 ? `-1 ${fail}` : String(chosen));
TypeScriptmain.ts · 62 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const shifts: [number, number][] = [];for (let i = 0; i < n; i++) shifts.push([data[3 + 2 * i], data[4 + 2 * i]]);shifts.sort((a, b) => a[0] - b[0]); // 비교 함수가 없으면 문자열로 견주어 10이 9보다 앞에 온다// TypeScript에도 힙이 없어서 배열로 최대 힙을 만든다. i의 자식은 2i+1, 2i+2function heapPush(heap: number[], x: number): void { heap.push(x); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (heap[parent] >= heap[i]) break; [heap[parent], heap[i]] = [heap[i], heap[parent]]; i = parent; }}function heapPop(heap: number[]): number { const top: number = heap[0]; const last = heap.pop(); if (last !== undefined && heap.length > 0) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let big = i; if (l < heap.length && heap[l] > heap[big]) big = l; if (r < heap.length && heap[r] > heap[big]) big = r; if (big === i) break; [heap[big], heap[i]] = [heap[i], heap[big]]; i = big; } } return top;}const cand: number[] = []; // 아직 뽑지 않았고 x칸 이전에 시작하는 사람들의 끝 칸(최대 힙)let active: number[] = []; // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개)let next = 0; // 아직 후보에 넣지 않은 첫 사람let chosen = 0;let x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸let fail = 0;while (x <= length && fail === 0) { while (next < n && shifts[next][0] <= x) heapPush(cand, shifts[next++][1]); active = active.filter((e: number) => e >= x); // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while (active.length < k) { if (cand.length === 0 || cand[0] < x) { fail = x; break; } active.push(heapPop(cand)); chosen++; } // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 if (fail === 0) x = Math.min(...active) + 1;}console.log(fail > 0 ? `-1 ${fail}` : String(chosen));
JavaMain.java · 40 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); st.nextToken(); int n = (int) st.nval; st.nextToken(); int length = (int) st.nval; st.nextToken(); int k = (int) st.nval; int[][] shifts = new int[n][2]; for (int i = 0; i < n; i++) { st.nextToken(); shifts[i][0] = (int) st.nval; st.nextToken(); shifts[i][1] = (int) st.nval; } Arrays.sort(shifts, (a, b) -> Integer.compare(a[0], b[0])); // PriorityQueue는 최소 힙이라 차례를 뒤집어 최대 힙으로 쓴다 PriorityQueue<Integer> cand = new PriorityQueue<>(Comparator.reverseOrder()); // 아직 뽑지 않은 후보들의 끝 칸 List<Integer> active = new ArrayList<>(); // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개) int next = 0, chosen = 0, fail = 0; int x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸 while (x <= length && fail == 0) { while (next < n && shifts[next][0] <= x) cand.add(shifts[next++][1]); final int now = x; active.removeIf(e -> e < now); // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while (active.size() < k) { if (cand.isEmpty() || cand.peek() < x) { fail = x; break; } active.add(cand.poll()); chosen++; } // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 if (fail == 0) x = Collections.min(active) + 1; } System.out.println(fail > 0 ? "-1 " + fail : String.valueOf(chosen)); }}
C#Main.cs · 44 줄
using System;using System.Collections.Generic;using System.Linq;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), length = int.Parse(data[1]), k = int.Parse(data[2]); var shifts = new (int Start, int End)[n]; for (int i = 0; i < n; i++) shifts[i] = (int.Parse(data[3 + 2 * i]), int.Parse(data[4 + 2 * i])); Array.Sort(shifts, (a, b) => a.Start.CompareTo(b.Start)); // PriorityQueue는 우선순위가 작은 것부터 꺼내니, 우선순위에 -끝 칸을 넣어 최대 힙으로 쓴다 var cand = new PriorityQueue<int, int>(); // 아직 뽑지 않은 후보들의 끝 칸 var active = new List<int>(); // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개) int next = 0, chosen = 0, fail = 0; int x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸 while (x <= length && fail == 0) { while (next < n && shifts[next].Start <= x) { cand.Enqueue(shifts[next].End, -shifts[next].End); next++; } active.RemoveAll(e => e < x); // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while (active.Count < k) { if (cand.Count == 0 || cand.Peek() < x) { fail = x; break; } active.Add(cand.Dequeue()); chosen++; } // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 if (fail == 0) x = active.Min() + 1; } Console.WriteLine(fail > 0 ? $"-1 {fail}" : chosen.ToString()); }}
C++main.cpp · 39 줄
#include <algorithm>#include <iostream>#include <queue>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, length, k; cin >> n >> length >> k; vector<pair<int, int>> shifts(n); // (시작 칸, 끝 칸) for (auto &s : shifts) cin >> s.first >> s.second; sort(shifts.begin(), shifts.end()); priority_queue<int> cand; // 아직 뽑지 않은 후보들의 끝 칸. priority_queue는 처음부터 최대 힙이다 vector<int> active; // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개) int next = 0, chosen = 0, fail = 0; int x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸 while (x <= length && fail == 0) { while (next < n && shifts[next].first <= x) cand.push(shifts[next++].second); active.erase(remove_if(active.begin(), active.end(), [x](int e) { return e < x; }), active.end()); // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while ((int)active.size() < k) { if (cand.empty() || cand.top() < x) { fail = x; break; } active.push_back(cand.top()); cand.pop(); chosen++; } // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 if (fail == 0) x = *min_element(active.begin(), active.end()) + 1; } if (fail > 0) cout << "-1 " << fail << '\n'; else cout << chosen << '\n'; return 0;}
Cmain.c · 87 줄
#include <stdio.h>#include <stdlib.h>#define MAXN 10000#define MAXK 5typedef struct { int start, end;} Shift;static Shift shifts[MAXN];static int heap[MAXN]; /* 최대 힙: heap[0]이 가장 크고, i의 자식은 2i+1, 2i+2 */static int heapSize = 0;static int byStart(const void *a, const void *b) { int x = ((const Shift *)a)->start, y = ((const Shift *)b)->start; return (x > y) - (x < y);}static void heapPush(int x) { int i = heapSize++; heap[i] = x; while (i > 0) { int parent = (i - 1) / 2; if (heap[parent] >= heap[i]) break; int t = heap[parent]; heap[parent] = heap[i]; heap[i] = t; i = parent; }}static int heapPop(void) { int top = heap[0]; heap[0] = heap[--heapSize]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, big = i; if (l < heapSize && heap[l] > heap[big]) big = l; if (r < heapSize && heap[r] > heap[big]) big = r; if (big == i) break; int t = heap[big]; heap[big] = heap[i]; heap[i] = t; i = big; } return top;}int main(void) { int n, length, k; if (scanf("%d %d %d", &n, &length, &k) != 3) return 1; for (int i = 0; i < n; i++) scanf("%d %d", &shifts[i].start, &shifts[i].end); qsort(shifts, (size_t)n, sizeof(Shift), byStart); int active[MAXK]; /* 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개) */ int activeCount = 0; int next = 0, chosen = 0, fail = 0; int x = 1; /* 아직 k명이 채워지지 않은 가장 앞 칸 */ while (x <= length && fail == 0) { while (next < n && shifts[next].start <= x) heapPush(shifts[next++].end); /* x칸보다 먼저 끝난 사람을 뺀다 */ int kept = 0; for (int i = 0; i < activeCount; i++) if (active[i] >= x) active[kept++] = active[i]; activeCount = kept; /* 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 */ while (activeCount < k) { if (heapSize == 0 || heap[0] < x) { fail = x; break; } active[activeCount++] = heapPop(); chosen++; } if (fail == 0) { /* 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 */ int first = active[0]; for (int i = 1; i < activeCount; i++) if (active[i] < first) first = active[i]; x = first + 1; } } if (fail > 0) printf("-1 %d\n", fail); else printf("%d\n", chosen); return 0;}
Craykonmain.cray · 127 줄
// 큰 수가 맨 위에 오는 최대 힙(목록 heap). heap[0]이 가장 크고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){ heap.넣기(x); i = heap.개수 - 1; 동안 (i > 0) { 부모 = 수학.몫(i - 1, 2); 만약 (heap[부모] >= heap[i]) { 그만; } t = heap[부모]; heap[부모] = heap[i]; heap[i] = t; i = 부모; }}힙빼기(heap){ top = heap[0]; heap[0] = heap[heap.개수 - 1]; heap.자리빼기(heap.개수 - 1); i = 0; 동안 (참) { l = 2 * i + 1; r = l + 1; big = i; 만약 (l < heap.개수 && heap[l] > heap[big]) { big = l; } 만약 (r < heap.개수 && heap[r] > heap[big]) { big = r; } 만약 (big == i) { 그만; } t = heap[big]; heap[big] = heap[i]; heap[i] = t; i = big; } 돌려주기 top;}첫줄 = 콘솔.수들읽기();n = 첫줄[0];length = 첫줄[1];k = 첫줄[2];starts = [];ends = [];order = [];반복 (i = 0; i < n; i++){ 줄 = 콘솔.수들읽기(); starts.넣기(줄[0]); ends.넣기(줄[1]); order.넣기(i);}// 시작 칸이 이른 사람부터 보도록 번호를 정렬한다byStart(a, b){ 돌려주기 starts[a] - starts[b];}order.정렬(byStart);cand = []; // 아직 뽑지 않았고 x칸 이전에 시작하는 사람들의 끝 칸(최대 힙)active = []; // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개)next = 0; // 아직 후보에 넣지 않은 첫 사람chosen = 0;x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸fail = 0;동안 (x <= length && fail == 0){ 동안 (next < n && starts[order[next]] <= x) { 힙넣기(cand, ends[order[next]]); next += 1; } // x칸보다 먼저 끝난 사람을 뺀다 still = []; 각각 (e 에서 active) { 만약 (e >= x) { still.넣기(e); } } active = still; // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 동안 (active.개수 < k) { 만약 (cand.개수 == 0 || cand[0] < x) { fail = x; 그만; } active.넣기(힙빼기(cand)); chosen += 1; } 만약 (fail == 0) { // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 first = active[0]; 각각 (e 에서 active) { first = 수학.작은수(first, e); } x = first + 1; }}만약 (fail > 0){ 콘솔.쓰기("-1 " + fail);}아니면{ 콘솔.쓰기(chosen);}