곧은 길이 0부터 L까지 놓여 있고, 길가에 가로등 n개가 있다.
i번째 가로등은 자리 pᵢ에 있고, 지금은 pᵢ − rᵢ부터 pᵢ + rᵢ까지(두 끝 포함)를 비춘다.
모든 가로등에 똑같은 세기 t의 증폭기를 달 수 있다.
t는 0 이상의 정수이고, 증폭기를 달면 모든 가로등이 pᵢ − rᵢ − t부터 pᵢ + rᵢ + t까지를 비춘다.
가로등은 많아야 k개만 켤 수 있다.
켠 가로등들이 비추는 구간을 합쳐서 0 이상 L 이하의 모든 점(정수가 아닌 점도 포함)이 비춰지면 길을 다 비춘 것이다.
두 구간이 끝점 하나에서만 만나도 그 사이에 틈은 없다.
길을 다 비출 수 있는 가장 작은 t를 출력하라.
입력
첫 줄에 n, L, k, 다음 n줄에 줄마다 pᵢ와 rᵢ가 빈칸으로 나뉘어 주어진다. 1 ≤ n ≤ 10,000, 0 ≤ L ≤ 1,000,000,000, 1 ≤ k ≤ n, 0 ≤ pᵢ ≤ L, 0 ≤ rᵢ ≤ 1,000,000,000
출력
가장 작은 t 하나
예시 1 · stdin
4 10 2
1 1
4 2
9 0
7 1
stdout
2
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
t를 키우면 모든 구간이 넓어지기만 하니, t에서 되면 t + 1에서도 돼요. 그래서 답 t를 이분 탐색해요: lo = 0, hi = L(t = L이면 길 위의 어느 가로등 하나로도 [0, L]을 다 비춰요)에서 mid가 되면 hi = mid, 안 되면 lo = mid + 1로 좁히면 lo가 답이에요. t 하나가 되는지는 욕심쟁이로 봐요: 아직 못 비춘 가장 왼쪽 점 need(처음엔 0)를 비출 수 있는 가로등 가운데 오른쪽 끝이 가장 먼 것을 켜고, need를 그 끝으로 옮기기를 k번까지 해요. 모든 구간이 똑같이 t만큼 늘어나니 왼쪽 끝 p − r의 차례는 t와 상관없어요 — 처음에 한 번만 정렬해 두면 검사마다 앞에서부터 한 번 훑으면 돼요(n log n + 31 × n). 함정 하나: 구간은 닫힌 구간이라 끝이 맞닿기만 해도 이어져요(왼쪽 끝 − t <= need). <로 쓰면 [−1, 5]와 [5, 11]이 이어지지 않는다고 봐서 답이 커져요. 함정 둘: p + r은 20억까지라 32비트 int(약 21억)에 겨우 들어가지만, 탐색 중에 t를 더하면 30억까지 가서 넘쳐요. C·C++ long long, Java·C# long이 필요하고, Python 정수는 끝이 없고, JavaScript·TypeScript·크레이콘의 수는 배정밀도 실수라 그대로 돼요. 함정 셋: 가로등을 자리 p 차례로 늘어놓으면 반지름이 다를 때 왼쪽 끝의 차례와 달라서, 앞에서부터 훑다가 왼쪽 끝이 더 작은 가로등을 놓쳐요. 함정 넷: 되는 mid를 hi = mid - 1로 버리면 답을 지나쳐요 — 답 후보는 [lo, hi] 안에 늘 남겨 둬요. 정렬은 언어마다 달라요: Python은 튜플 (p - r, p + r)을 그대로 sort(), JavaScript·TypeScript는 sort((x, y) => x[0] - y[0])(비교 함수가 없으면 문자열로 비교해요), Java Arrays.sort(lamps, (x, y) -> Long.compare(x[0], y[0])), C# Array.Sort(lamps, (x, y) => x.left.CompareTo(y.left)), C++는 std::pair를 그대로 std::sort, C qsort는 비교 함수에서 x - y를 int로 돌려주면 넘칠 수 있어서 (x > y) - (x < y)로 돌려줘요. 크레이콘은 lamps.정렬(왼쪽끝순)처럼 음수·0·양수를 돌려주는 함수를 넘기고, 정수 나눗셈은 수학.몫(lo + hi, 2)예요.
Pythonmain.py · 40 줄
import sysdata = sys.stdin.read().split()n, length, k = int(data[0]), int(data[1]), int(data[2])lamps = [] # (p - r, p + r): 늘이기 전에 비추는 구간for i in range(n): p, r = int(data[3 + 2 * i]), int(data[4 + 2 * i]) lamps.append((p - r, p + r))lamps.sort() # 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다def lamps_needed_ok(t): """모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가.""" need = 0 # 아직 비춘다고 확인하지 못한 가장 왼쪽 점 i = 0 best = -1 # 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 used = 0 while used < k: while i < n and lamps[i][0] - t <= need: # 끝이 닿기만 해도 이어진다(닫힌 구간) best = max(best, lamps[i][1] + t) i += 1 if best < need: # need를 비추는 등이 없다 return False used += 1 if best >= length: return True if best == need: # 더 나아갈 수 없다 return False need = best return Falselo, hi = 0, length # t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while lo < hi: mid = (lo + hi) // 2 if lamps_needed_ok(mid): hi = mid else: lo = mid + 1print(lo)
JavaScriptmain.js · 34 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const lamps = []; // [p - r, p + r]: 늘이기 전에 비추는 구간for (let i = 0; i < n; i++) { const p = data[3 + 2 * i], r = data[4 + 2 * i]; lamps.push([p - r, p + r]);}lamps.sort((x, y) => x[0] - y[0]); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다// 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가function canCover(t) { let need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 let i = 0; let best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (let used = 1; used <= k; used++) { while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = Math.max(best, lamps[i][1] + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best === need) return false; // 더 나아갈 수 없다 need = best; } return false;}let lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (canCover(mid)) hi = mid; else lo = mid + 1;}console.log(lo);
TypeScriptmain.ts · 36 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const lamps: [left: number, right: number][] = []; // 늘이기 전에 비추는 구간 [p - r, p + r]for (let i = 0; i < n; i++) { const p = data[3 + 2 * i], r = data[4 + 2 * i]; lamps.push([p - r, p + r]);}lamps.sort((x, y) => x[0] - y[0]); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다// 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가function canCover(t: number): boolean { let need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 let i = 0; let best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (let used = 1; used <= k; used++) { while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = Math.max(best, lamps[i][1] + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best === need) return false; // 더 나아갈 수 없다 need = best; } return false;}let lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while (lo < hi) { const mid: number = Math.floor((lo + hi) / 2); if (canCover(mid)) hi = mid; else lo = mid + 1;}console.log(lo);
JavaMain.java · 54 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int n, k; static long length; static long[][] lamps; // {p - r, p + r}: 늘이기 전에 비추는 구간. p + r + t는 30억까지라 long // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가 static boolean canCover(long t) { long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 int i = 0; long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (int used = 1; used <= k; used++) { while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = Math.max(best, lamps[i][1] + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best == need) return false; // 더 나아갈 수 없다 need = best; } return false; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); n = Integer.parseInt(st.nextToken()); length = Long.parseLong(st.nextToken()); k = Integer.parseInt(st.nextToken()); lamps = new long[n][]; for (int i = 0; i < n; i++) { st = new StringTokenizer(in.readLine()); long p = Long.parseLong(st.nextToken()); long r = Long.parseLong(st.nextToken()); lamps[i] = new long[] {p - r, p + r}; } // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 Arrays.sort(lamps, (x, y) -> Long.compare(x[0], y[0])); long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 while (lo < hi) { long mid = (lo + hi) / 2; if (canCover(mid)) hi = mid; else lo = mid + 1; } System.out.println(lo); }}
C#Main.cs · 55 줄
using System;class Program{ static int n, k; static long length; static (long left, long right)[] lamps; // 늘이기 전에 비추는 구간 [p - r, p + r]. p + r + t는 30억까지라 long // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가 static bool CanCover(long t) { long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 int i = 0; long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (int used = 1; used <= k; used++) { while (i < n && lamps[i].left - t <= need) // 끝이 닿기만 해도 이어진다(닫힌 구간) { best = Math.Max(best, lamps[i].right + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best == need) return false; // 더 나아갈 수 없다 need = best; } return false; } static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); n = int.Parse(first[0]); length = long.Parse(first[1]); k = int.Parse(first[2]); lamps = new (long left, long right)[n]; for (int i = 0; i < n; i++) { string[] w = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long p = long.Parse(w[0]), r = long.Parse(w[1]); lamps[i] = (p - r, p + r); } // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 Array.Sort(lamps, (x, y) => x.left.CompareTo(y.left)); long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 while (lo < hi) { long mid = (lo + hi) / 2; if (CanCover(mid)) hi = mid; else lo = mid + 1; } Console.WriteLine(lo); }}
C++main.cpp · 48 줄
#include <algorithm>#include <iostream>#include <utility>#include <vector>int n, k;long long length;std::vector<std::pair<long long, long long>> lamps; // (p - r, p + r): 늘이기 전에 비추는 구간. p + r + t는 30억까지라 long long// 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가bool canCover(long long t) { long long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 int i = 0; long long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (int used = 1; used <= k; used++) { while (i < n && lamps[i].first - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = std::max(best, lamps[i].second + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best == need) return false; // 더 나아갈 수 없다 need = best; } return false;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> n >> length >> k; lamps.resize(n); for (auto& lamp : lamps) { long long p, r; std::cin >> p >> r; lamp = {p - r, p + r}; } std::sort(lamps.begin(), lamps.end()); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 long long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 while (lo < hi) { long long mid = (lo + hi) / 2; if (canCover(mid)) hi = mid; else lo = mid + 1; } std::cout << lo << '\n'; return 0;}
Cmain.c · 55 줄
#include <stdio.h>#include <stdlib.h>#define MAXN 10000typedef struct { long long left, right; /* 늘이기 전에 비추는 구간 [p - r, p + r]. p + r + t는 30억까지라 long long */} Lamp;static Lamp lamps[MAXN];static int n, k;static long long length;static int byLeft(const void* a, const void* b) { long long x = ((const Lamp*)a)->left, y = ((const Lamp*)b)->left; return (x > y) - (x < y); /* x - y를 int로 돌려주면 넘칠 수 있다 */}/* 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있으면 1 */static int canCover(long long t) { long long need = 0; /* 아직 비춘다고 확인하지 못한 가장 왼쪽 점 */ long long best = -1; /* 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 */ int i = 0; for (int used = 1; used <= k; used++) { while (i < n && lamps[i].left - t <= need) { /* 끝이 닿기만 해도 이어진다(닫힌 구간) */ if (lamps[i].right + t > best) best = lamps[i].right + t; i++; } if (best < need) return 0; /* need를 비추는 등이 없다 */ if (best >= length) return 1; if (best == need) return 0; /* 더 나아갈 수 없다 */ need = best; } return 0;}int main(void) { if (scanf("%d %lld %d", &n, &length, &k) != 3) return 0; for (int i = 0; i < n; i++) { long long p, r; scanf("%lld %lld", &p, &r); lamps[i].left = p - r; lamps[i].right = p + r; } qsort(lamps, n, sizeof lamps[0], byLeft); /* 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 */ long long lo = 0, hi = length; /* t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 */ while (lo < hi) { long long mid = (lo + hi) / 2; if (canCover(mid)) hi = mid; else lo = mid + 1; } printf("%lld\n", lo); return 0;}
Craykonmain.cray · 62 줄
// 모든 등을 t만큼 늘였을 때 k개 이하로 [0, 길이]를 다 비출 수 있는가비출수있나(lamps, 길이, k, t){ need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 i = 0; best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 반복 (used = 1; used <= k; used++) { 동안 (i < lamps.개수 && lamps[i][0] - t <= need) { best = 수학.큰수(best, lamps[i][1] + t); i++; } 만약 (best < need) { 돌려주기 거짓; } 만약 (best >= 길이) { 돌려주기 참; } 만약 (best == need) { 돌려주기 거짓; } need = best; } 돌려주기 거짓;}왼쪽끝순(앞, 뒤){ 돌려주기 앞[0] - 뒤[0];}첫줄 = 콘솔.수들읽기();n = 첫줄[0];길이 = 첫줄[1];k = 첫줄[2];lamps = []; // [p - r, p + r]: 늘이기 전에 비추는 구간반복 (j = 0; j < n; j++){ 등 = 콘솔.수들읽기(); lamps.넣기([등[0] - 등[1], 등[0] + 등[1]]);}lamps.정렬(왼쪽끝순); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다lo = 0;hi = 길이; // t = 길이이면 어느 등 하나로도 [0, 길이]를 다 비춘다동안 (lo < hi){ mid = 수학.몫(lo + hi, 2); 만약 (비출수있나(lamps, 길이, k, mid)) { hi = mid; } 아니면 { lo = mid + 1; }}콘솔.쓰기(lo);