바닷가를 따라 난 길에 높이 표지가 n개 서 있다.
i번째 표지는 길의 시작에서 x_i만큼 떨어진 곳에 있고, 그곳의 높이는 h_i이다.
높이는 바닷물 높이를 0으로 잰 값이라서 음수일 수도 있다.
표지는 시작에서 가까운 것부터 주어지고, 같은 곳에 표지가 둘 있지는 않다.
이웃한 두 표지 사이에서는 길이 곧게 이어진다고 본다.
곧, 표지 (x0, h0)과 다음 표지 (x1, h1) 사이의 거리 d에서 높이는 h0 + (d - x0) × (h1 - h0) ÷ (x1 - x0)이다.
첫 표지보다 앞에서는 첫 표지의 높이로, 마지막 표지보다 뒤에서는 마지막 표지의 높이로 본다.
거리 d가 q개 주어질 때, 그 거리에서의 높이를 넘지 않는 가장 큰 정수를 각각 구하라.
높이가 68.5이면 68이고, -0.25이면 0이 아니라 -1이다.
예제에서 거리 17은 (10, 100)과 (20, 55) 사이이므로 높이는 100 + 7 × (-45) ÷ 10 = 68.5이고 답은 68이다.
거리 33은 (20, 55)와 (40, -30) 사이이므로 높이는 55 + 13 × (-85) ÷ 20 = -0.25이고 답은 -1이다.
입력
첫 줄에 n과 q가 빈칸으로 나뉘어 주어진다. 다음 n줄에 표지가 한 줄에 하나씩 "x h" 꼴로 주어진다. 마지막 줄에 거리 d가 q개 빈칸 하나로 나뉘어 주어진다. 모든 수는 정수다. 1 ≤ n ≤ 10,000, 1 ≤ q ≤ 10,000, 0 ≤ x_1 < x_2 < … < x_n ≤ 1,000,000,000, -1,000,000 ≤ h_i ≤ 1,000,000, 0 ≤ d ≤ 1,000,000,000
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
먼저 d가 어느 두 표지 사이인지 이분 탐색으로 찾아요: 'x가 d 이하인 마지막 표지'의 번호예요. Python은 bisect_right(xs, d) - 1, C++은 std::upper_bound에서 한 칸 앞이에요. Java Arrays.binarySearch는 못 찾으면 -(끼울 자리) - 1을 돌려줘서 -p - 2로 바꾸고, C# Array.BinarySearch는 끼울 자리의 비트를 뒤집은 수를 돌려줘서 ~p - 1로 바꿔요. JS·TS·C·크레이콘은 lo, hi로 직접 써요. 함정 하나: 내리막에서는 나누어지는 수가 음수예요. C·C++·Java·C#의 정수 /는 내림이 아니라 0 쪽으로 버려서 -315 / 10이 -31이에요(답은 -32). 예제의 거리 17이 69, 거리 33이 0으로 나와요. Python //는 내림이라 그대로 맞고, Java는 Math.floorDiv, JS·TS는 Math.floor(a / b), C·C++·C#은 나머지가 음수일 때 몫에서 1을 빼요. 크레이콘의 수학.몫도 0 쪽으로 버리므로 수학.내림(a / b)를 써요. 높이를 가중 평균 (h0 × (x1 - d) + h1 × (d - x0)) ÷ (x1 - x0)으로 바꿔도 높이가 음수이면 같은 일이 생겨요(예제의 거리 46: -447 ÷ 15는 -29.8이라 답은 -30인데 버리면 -29). 함정 둘: 거리 차와 높이 차의 곱은 2,000조까지 커져요. Java·C#의 int는 오류 없이 엉뚱한 수가 되고 C·C++은 정의되지 않은 동작이니 long·long long으로 곱해요. JS·TS·크레이콘의 수는 2^53(약 9,000조)까지 정확해서 그대로 돼요. 함정 셋: 넘칠까 봐 먼저 나누고 나중에 곱하면 기울기의 소수 부분이 사라져요. 곱한 뒤에 나눠요. 함정 넷: 첫 표지보다 앞이면 번호가 -1이에요. Python은 xs[-1]이 오류 없이 마지막 표지를 주므로 따로 갈라야 해요. 함정 다섯: 이분 탐색의 범위에서 마지막 표지를 빼면, 마지막 표지 뒤에서도 앞 구간의 기울기로 계속 올라가거나 내려가요.
Pythonmain.py · 22 줄
import sysfrom bisect import bisect_rightdef main(): data = sys.stdin.read().split() n, q = int(data[0]), int(data[1]) xs = [int(v) for v in data[2:2 + 2 * n:2]] hs = [int(v) for v in data[3:3 + 2 * n:2]] out = [] for v in data[2 + 2 * n:2 + 2 * n + q]: d = int(v) i = bisect_right(xs, d) - 1 # d 이하인 마지막 표지 (없으면 -1) if i < 0: out.append(hs[0]) # 첫 표지보다 앞 elif i == n - 1: out.append(hs[n - 1]) # 마지막 표지이거나 그 뒤 else: # //는 음수에서도 내림이다: -85 // 10 == -9 out.append(hs[i] + (d - xs[i]) * (hs[i + 1] - hs[i]) // (xs[i + 1] - xs[i])) print("\n".join(map(str, out)))main()
JavaScriptmain.js · 34 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const n = data[0];const q = data[1];const xs = [];const hs = [];for (let i = 0; i < n; i++) { xs.push(data[2 + 2 * i]); hs.push(data[3 + 2 * i]);}// d 이하인 마지막 표지의 번호 (없으면 -1)function lastAtOrBefore(d) { let lo = 0; let hi = n; // xs[lo..hi) 가운데 d보다 큰 첫 칸을 찾는다 while (lo < hi) { const mid = (lo + hi) >> 1; if (xs[mid] <= d) lo = mid + 1; else hi = mid; } return lo - 1;}const out = [];for (let k = 0; k < q; k++) { const d = data[2 + 2 * n + k]; const i = lastAtOrBefore(d); if (i < 0) out.push(hs[0]); else if (i === n - 1) out.push(hs[n - 1]); else { // 곱이 2^53보다 작아 정확하고, Math.floor는 음수에서도 내림이다 out.push(hs[i] + Math.floor(((d - xs[i]) * (hs[i + 1] - hs[i])) / (xs[i + 1] - xs[i]))); }}console.log(out.join("\n"));
TypeScriptmain.ts · 35 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const n: number = data[0];const q: number = data[1];const xs: number[] = [];const hs: number[] = [];for (let i = 0; i < n; i++) { xs.push(data[2 + 2 * i]); hs.push(data[3 + 2 * i]);}// d 이하인 마지막 표지의 번호 (없으면 -1)function lastAtOrBefore(d: number): number { let lo = 0; let hi = n; // xs[lo..hi) 가운데 d보다 큰 첫 칸을 찾는다 while (lo < hi) { const mid = (lo + hi) >> 1; if (xs[mid] <= d) lo = mid + 1; else hi = mid; } return lo - 1;}const out: number[] = [];for (let k = 0; k < q; k++) { const d = data[2 + 2 * n + k]; const i = lastAtOrBefore(d); if (i < 0) out.push(hs[0]); else if (i === n - 1) out.push(hs[n - 1]); else { // 곱이 2^53보다 작아 정확하고, Math.floor는 음수에서도 내림이다 out.push(hs[i] + Math.floor(((d - xs[i]) * (hs[i + 1] - hs[i])) / (xs[i + 1] - xs[i]))); }}console.log(out.join("\n"));
JavaMain.java · 40 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.StreamTokenizer;import java.util.Arrays;public class Main { public static void main(String[] args) throws Exception { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; in.nextToken(); int q = (int) in.nval; int[] xs = new int[n]; long[] hs = new long[n]; for (int i = 0; i < n; i++) { in.nextToken(); xs[i] = (int) in.nval; in.nextToken(); hs[i] = (long) in.nval; } StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { in.nextToken(); int d = (int) in.nval; // 찾으면 그 번호, 못 찾으면 -(끼울 자리) - 1 을 돌려준다 int p = Arrays.binarySearch(xs, d); int i = p >= 0 ? p : -p - 2; // d 이하인 마지막 표지 (없으면 -1) long ans; if (i < 0) ans = hs[0]; else if (i == n - 1) ans = hs[n - 1]; else { // long으로 곱하고, 음수에서도 내림인 floorDiv를 쓴다 (/ 는 0 쪽으로 버린다) long num = (long) (d - xs[i]) * (hs[i + 1] - hs[i]); ans = hs[i] + Math.floorDiv(num, (long) (xs[i + 1] - xs[i])); } out.append(ans).append('\n'); } System.out.print(out); }}
C#Main.cs · 40 줄
using System;using System.Text;class Program{ // C#의 / 는 0 쪽으로 버리므로 내림 나눗셈을 직접 만든다 (b > 0) static long FloorDiv(long a, long b) { long quot = a / b; if (a % b < 0) quot--; return quot; } static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), q = int.Parse(data[1]); int[] xs = new int[n]; long[] hs = new long[n]; for (int i = 0; i < n; i++) { xs[i] = int.Parse(data[2 + 2 * i]); hs[i] = long.Parse(data[3 + 2 * i]); } var sb = new StringBuilder(); for (int k = 0; k < q; k++) { int d = int.Parse(data[2 + 2 * n + k]); // 찾으면 그 번호, 못 찾으면 끼울 자리의 비트를 뒤집은 수(~자리)를 돌려준다 int p = Array.BinarySearch(xs, d); int i = p >= 0 ? p : ~p - 1; // d 이하인 마지막 표지 (없으면 -1) long ans; if (i < 0) ans = hs[0]; else if (i == n - 1) ans = hs[n - 1]; else ans = hs[i] + FloorDiv((long)(d - xs[i]) * (hs[i + 1] - hs[i]), xs[i + 1] - xs[i]); sb.Append(ans).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 31 줄
#include <algorithm>#include <iostream>#include <vector>// C++의 / 는 0 쪽으로 버리므로 내림 나눗셈을 직접 만든다 (b > 0)long long floorDiv(long long a, long long b) { long long quot = a / b; if (a % b < 0) quot--; return quot;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<int> xs(n); std::vector<long long> hs(n); for (int i = 0; i < n; i++) std::cin >> xs[i] >> hs[i]; for (int k = 0; k < q; k++) { int d; std::cin >> d; // upper_bound: d보다 큰 첫 칸 → 그 앞 칸이 d 이하인 마지막 표지 (없으면 -1) int i = static_cast<int>(std::upper_bound(xs.begin(), xs.end(), d) - xs.begin()) - 1; long long ans; if (i < 0) ans = hs[0]; else if (i == n - 1) ans = hs[n - 1]; else ans = hs[i] + floorDiv(static_cast<long long>(d - xs[i]) * (hs[i + 1] - hs[i]), xs[i + 1] - xs[i]); std::cout << ans << '\n'; }}
Cmain.c · 34 줄
#include <stdio.h>int xs[10000];long long hs[10000];/* C의 / 는 0 쪽으로 버리므로 내림 나눗셈을 직접 만든다 (b > 0) */long long floor_div(long long a, long long b) { long long quot = a / b; if (a % b < 0) quot--; return quot;}int main(void) { int n, q; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) scanf("%d %lld", &xs[i], &hs[i]); for (int k = 0; k < q; k++) { int d; scanf("%d", &d); int lo = 0, hi = n; /* xs[lo..hi) 가운데 d보다 큰 첫 칸을 찾는다 */ while (lo < hi) { int mid = (lo + hi) / 2; if (xs[mid] <= d) lo = mid + 1; else hi = mid; } int i = lo - 1; /* d 이하인 마지막 표지 (없으면 -1) */ long long ans; if (i < 0) ans = hs[0]; else if (i == n - 1) ans = hs[n - 1]; else ans = hs[i] + floor_div((long long)(d - xs[i]) * (hs[i + 1] - hs[i]), xs[i + 1] - xs[i]); printf("%lld\n", ans); } return 0;}
Craykonmain.cray · 50 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];q = 첫줄[1];xs = [];hs = [];반복 (i = 0; i < n; i++){ 줄 = 콘솔.수들읽기(); xs.넣기(줄[0]); hs.넣기(줄[1]);}// d 이하인 마지막 표지의 번호 (없으면 -1)마지막표지(d){ lo = 0; hi = n; // xs[lo..hi) 가운데 d보다 큰 첫 칸을 찾는다 동안 (lo < hi) { mid = 수학.몫(lo + hi, 2); 만약 (xs[mid] <= d) { lo = mid + 1; } 아니면 { hi = mid; } } 돌려주기 lo - 1;}질문 = 콘솔.수들읽기();각각 (d 에서 질문){ i = 마지막표지(d); 만약 (i < 0) { 콘솔.쓰기(hs[0]); } 아니면 만약 (i == n - 1) { 콘솔.쓰기(hs[n - 1]); } 아니면 { // 수학.몫은 0 쪽으로 버리므로, 실수로 나눈 뒤 수학.내림으로 내린다 콘솔.쓰기(hs[i] + 수학.내림((d - xs[i]) * (hs[i + 1] - hs[i]) / (xs[i + 1] - xs[i]))); }}