역 m + 1개가 한 줄로 놓여 있고, i번 구간(1 ≤ i ≤ m)의 열차는 i번째 역에서 i + 1번째 역까지만 간다.
끝 역까지 가려면 1번 구간부터 m번 구간까지 구간마다 열차를 꼭 한 번씩 차례로 타야 한다.
구간마다 열차 시각표가 있고, 열차 하나는 출발 시각과 걸리는 시간으로 적혀 있다.
열차는 출발 시각에 걸리는 시간을 더한 시각에 다음 역에 닿는다.
한 구간 안에서 출발 시각은 모두 다르지만, 빠른 열차가 있어서 나중에 떠난 열차가 먼저 닿을 수도 있다.
어떤 역에 시각 x에 있으면 그 역에서 출발 시각이 x 이상인 열차를 탈 수 있다(닿은 시각과 같은 시각에 떠나는 열차도 탈 수 있다).
질문 q개에 답하라.
질문 "A t"는 첫 역에 시각 t에 있을 때 끝 역에 닿을 수 있는 가장 이른 시각을 묻는다.
질문 "B d"는 끝 역에 시각 d 이하에 닿으려면 1번 구간에서 타는 열차의 출발 시각이 가장 늦게는 얼마일 수 있는지를 묻는다.
질문마다 답을 한 줄에 하나씩 출력한다.
질문 A에서 끝 역까지 갈 방법이 없거나, 질문 B에서 끝 역에 시각 d 이하에 닿을 방법이 없으면 -1을 출력한다.
입력
첫 줄에 m과 q가 빈칸으로 나뉘어 주어진다. 이어서 1번 구간부터 차례로 구간마다 세 줄이 주어진다: 열차 수 c, 출발 시각 c개(커지는 차례, 빈칸 하나로 나뉨), 걸리는 시간 c개(출발 시각과 같은 차례). 다음 q줄에 질문 "A t" 또는 "B d"가 한 줄에 하나씩 주어진다. 1 ≤ m ≤ 10, 1 ≤ c, 모든 구간의 c를 더한 값 ≤ 10,000, 1 ≤ q ≤ 5,000, 0 ≤ 출발 시각 ≤ 2,000,000,000, 1 ≤ 걸리는 시간 ≤ 1,000,000,000, 0 ≤ t, d ≤ 3,000,000,000
출력
q줄. 질문 A에는 끝 역에 닿는 가장 이른 시각, 질문 B에는 1번 구간 열차의 가장 늦은 출발 시각, 갈 수 없으면 -1. 수는 쉼표 없이 숫자만 쓴다
예시 1 · stdin
2 6
3
10 20 30
50 15 20
3
35 50 60
10 20 5
A 5
A 25
A 31
B 45
B 65
B 44
stdout
45
65
-1
20
30
-1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
이분 탐색은 '어느 자리부터 조건이 참으로 바뀌는가'를 찾는 일이라 목록이 한쪽으로만 커져야 해요. 출발 시각은 정렬되어 있지만 도착 시각은 앞지르기 때문에 뒤죽박죽이에요. 그래서 뒤에서부터 최솟값을 누적해 'j번째나 그 뒤 열차를 탔을 때 가장 이른 도착'을 만들어 두면, 이 목록은 커지기만 해서 이분 탐색을 할 수 있고 질문 A의 답도 바로 여기서 읽어요. 질문 A는 '출발 ≥ 지금 시각인 첫 자리'(lower bound), 질문 B는 '누적 도착 ≤ 기한인 마지막 자리'(upper bound의 바로 앞)예요. 도구는 언어마다 달라요: Python bisect_left·bisect_right, C++ std::lower_bound·std::upper_bound가 딱 맞아요. Java Arrays.binarySearch와 C# Array.BinarySearch는 값이 없으면 들어갈 자리를 음수로 바꿔 돌려주고(Java는 -(자리) - 1, C#은 ~자리), 같은 값이 여럿이면 그중 어느 것을 줄지 정해져 있지 않아서 누적 도착처럼 같은 값이 늘어선 목록에는 직접 짠 것이 안전해요. C bsearch는 꼭 같은 값만 찾고 없으면 NULL이라 여기에 못 써요. JS·TS와 크레이콘에는 없어서 직접 짜요(크레이콘은 수학.몫(lo + hi, 2)로 가운데를 구해요). 함정 하나: 탈 수 있는 첫 열차를 그냥 타면 틀려요. 뒤에 떠나는 급행이 먼저 닿을 수 있어요. 함정 둘: 누적하지 않은 도착 시각에 이분 탐색을 하면 오류 없이 엉뚱한 자리가 나와요. 함정 셋: 경계예요. 닿은 시각과 같은 시각에 떠나는 열차를 탈 수 있고(>=), 기한과 같은 시각에 닿아도 돼요(<=). lower bound와 upper bound를 바꿔 쓰면 딱 이 경우만 틀려요. 함정 넷: 출발 시각 20억은 32비트 int에 들어가지만 걸리는 시간을 더한 30억은 넘쳐요. Java·C#은 오류 없이 음수가 되고 C·C++은 정의되지 않은 동작이니 long·long long으로 받아요. 질문의 t와 d도 30억까지라 int로는 읽지도 못해요. Python, JS·TS, 크레이콘은 그대로 돼요.
Pythonmain.py · 50 줄
import sysfrom bisect import bisect_left, bisect_rightdef main(): data = sys.stdin.buffer.read().split() m, q = int(data[0]), int(data[1]) pos = 2 deps = [] # deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례) best = [] # best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for _ in range(m): c = int(data[pos]) pos += 1 dep = [int(x) for x in data[pos : pos + c]] pos += c arr = [dep[j] + int(data[pos + j]) for j in range(c)] pos += c # 뒤에서부터 최솟값을 누적하면 커지기만 하는 목록이 되어 이분 탐색을 할 수 있다 for j in range(c - 2, -1, -1): if arr[j + 1] < arr[j]: arr[j] = arr[j + 1] deps.append(dep) best.append(arr) out = [] for _ in range(q): kind = data[pos] x = int(data[pos + 1]) pos += 2 if kind == b"A": # 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for i in range(m): j = bisect_left(deps[i], x) if j == len(deps[i]): x = -1 break x = best[i][j] else: # 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for i in range(m - 1, -1, -1): j = bisect_right(best[i], x) - 1 if j < 0: x = -1 break x = deps[i][j] out.append(x) print("\n".join(map(str, out)))main()
JavaScriptmain.js · 70 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [m, q] = lines[0].trim().split(/\s+/).map(Number);const deps = []; // deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례)const best = []; // best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각let row = 1;for (let i = 0; i < m; i++) { const c = Number(lines[row].trim()); const dep = lines[row + 1].trim().split(/\s+/).map(Number); const dur = lines[row + 2].trim().split(/\s+/).map(Number); row += 3; const arr = dep.map((t, j) => t + dur[j]); // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (let j = c - 2; j >= 0; j--) arr[j] = Math.min(arr[j], arr[j + 1]); deps.push(dep); best.push(arr);}// a[j] >= x인 첫 자리(없으면 a.length)function lowerBound(a, x) { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo;}// a[j] > x인 첫 자리(없으면 a.length)function upperBound(a, x) { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo;}const out = [];for (let k = 0; k < q; k++) { const [kind, value] = lines[row + k].trim().split(/\s+/); let x = Number(value); if (kind === "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (let i = 0; i < m; i++) { const j = lowerBound(deps[i], x); if (j === deps[i].length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (let i = m - 1; i >= 0; i--) { const j = upperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } out.push(x);}console.log(out.join("\n"));
TypeScriptmain.ts · 72 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [m, q] = lines[0].trim().split(/\s+/).map(Number);const deps: number[][] = []; // deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례)const best: number[][] = []; // best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각let row = 1;for (let i = 0; i < m; i++) { const c = Number(lines[row].trim()); const dep: number[] = lines[row + 1].trim().split(/\s+/).map(Number); const dur: number[] = lines[row + 2].trim().split(/\s+/).map(Number); row += 3; const arr: number[] = dep.map((t, j) => t + dur[j]); // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (let j = c - 2; j >= 0; j--) arr[j] = Math.min(arr[j], arr[j + 1]); deps.push(dep); best.push(arr);}// a[j] >= x인 첫 자리(없으면 a.length)function lowerBound(a: number[], x: number): number { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo;}// a[j] > x인 첫 자리(없으면 a.length)function upperBound(a: number[], x: number): number { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo;}const out: number[] = [];for (let k = 0; k < q; k++) { const [kind, value] = lines[row + k].trim().split(/\s+/); let x = Number(value); if (kind === "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (let i = 0; i < m; i++) { const j = lowerBound(deps[i], x); if (j === deps[i].length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (let i = m - 1; i >= 0; i--) { const j = upperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } out.push(x);}console.log(out.join("\n"));
JavaMain.java · 80 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { // a[j] >= x인 첫 자리(없으면 a.length) static int lowerBound(long[] a, long x) { int lo = 0, hi = a.length; while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo; } // a[j] > x인 첫 자리(없으면 a.length) static int upperBound(long[] a, long x) { int lo = 0, hi = a.length; while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); // 도착 시각은 30억까지 가므로 long이어야 한다 long[][] deps = new long[m][]; // 출발 시각(커지는 차례) long[][] best = new long[m][]; // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c = Integer.parseInt(br.readLine().trim()); deps[i] = new long[c]; best[i] = new long[c]; st = new StringTokenizer(br.readLine()); for (int j = 0; j < c; j++) deps[i][j] = Long.parseLong(st.nextToken()); st = new StringTokenizer(br.readLine()); for (int j = 0; j < c; j++) best[i][j] = deps[i][j] + Long.parseLong(st.nextToken()); // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) best[i][j] = Math.min(best[i][j], best[i][j + 1]); } StringBuilder sb = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(br.readLine()); String kind = st.nextToken(); long x = Long.parseLong(st.nextToken()); if (kind.equals("A")) { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (int i = 0; i < m; i++) { int j = lowerBound(deps[i], x); if (j == deps[i].length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (int i = m - 1; i >= 0; i--) { int j = upperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } sb.append(x).append('\n'); } System.out.print(sb); }}
C#Main.cs · 94 줄
using System;using System.Text;class Program{ // a[j] >= x인 첫 자리(없으면 a.Length) static int LowerBound(long[] a, long x) { int lo = 0, hi = a.Length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo; } // a[j] > x인 첫 자리(없으면 a.Length) static int UpperBound(long[] a, long x) { int lo = 0, hi = a.Length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo; } static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int m = int.Parse(first[0]); int q = int.Parse(first[1]); // 도착 시각은 30억까지 가므로 long이어야 한다 long[][] deps = new long[m][]; // 출발 시각(커지는 차례) long[][] best = new long[m][]; // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c = int.Parse(Console.ReadLine()); string[] d = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); string[] u = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); deps[i] = new long[c]; best[i] = new long[c]; for (int j = 0; j < c; j++) { deps[i][j] = long.Parse(d[j]); best[i][j] = deps[i][j] + long.Parse(u[j]); } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) best[i][j] = Math.Min(best[i][j], best[i][j + 1]); } var sb = new StringBuilder(); for (int k = 0; k < q; k++) { string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long x = long.Parse(t[1]); if (t[0] == "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (int i = 0; i < m; i++) { int j = LowerBound(deps[i], x); if (j == deps[i].Length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (int i = m - 1; i >= 0; i--) { int j = UpperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } sb.Append(x).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 58 줄
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, q; cin >> m >> q; // 도착 시각은 30억까지 가므로 long long이어야 한다 vector<vector<long long>> deps(m); // 출발 시각(커지는 차례) vector<vector<long long>> best(m); // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c; cin >> c; deps[i].resize(c); best[i].resize(c); for (auto& t : deps[i]) cin >> t; for (int j = 0; j < c; j++) { long long dur; cin >> dur; best[i][j] = deps[i][j] + dur; } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) best[i][j] = min(best[i][j], best[i][j + 1]); } for (int k = 0; k < q; k++) { char kind; long long x; cin >> kind >> x; if (kind == 'A') { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차 → lower_bound for (int i = 0; i < m; i++) { auto it = lower_bound(deps[i].begin(), deps[i].end(), x); if (it == deps[i].end()) { x = -1; break; } x = best[i][it - deps[i].begin()]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차 → upper_bound의 바로 앞 for (int i = m - 1; i >= 0; i--) { auto it = upper_bound(best[i].begin(), best[i].end(), x); if (it == best[i].begin()) { x = -1; break; } x = deps[i][it - best[i].begin() - 1]; } } cout << x << '\n'; } return 0;}
Cmain.c · 85 줄
#include <stdio.h>#include <stdlib.h>// a[j] >= x인 첫 자리(없으면 n)static int lower_bound(const long long *a, int n, long long x) { int lo = 0, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo;}// a[j] > x인 첫 자리(없으면 n)static int upper_bound(const long long *a, int n, long long x) { int lo = 0, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo;}int main(void) { int m, q; if (scanf("%d %d", &m, &q) != 2) return 1; // 도착 시각은 30억까지 가므로 long long이어야 한다 int cnt[10]; long long *deps[10]; // 출발 시각(커지는 차례) long long *best[10]; // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c; scanf("%d", &c); cnt[i] = c; deps[i] = malloc(sizeof(long long) * c); best[i] = malloc(sizeof(long long) * c); for (int j = 0; j < c; j++) scanf("%lld", &deps[i][j]); for (int j = 0; j < c; j++) { long long dur; scanf("%lld", &dur); best[i][j] = deps[i][j] + dur; } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) { if (best[i][j + 1] < best[i][j]) best[i][j] = best[i][j + 1]; } } for (int k = 0; k < q; k++) { char kind; long long x; scanf(" %c %lld", &kind, &x); if (kind == 'A') { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (int i = 0; i < m; i++) { int j = lower_bound(deps[i], cnt[i], x); if (j == cnt[i]) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (int i = m - 1; i >= 0; i--) { int j = upper_bound(best[i], cnt[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } printf("%lld\n", x); } for (int i = 0; i < m; i++) { free(deps[i]); free(best[i]); } return 0;}
Craykonmain.cray · 98 줄
첫줄 = 콘솔.수들읽기();m = 첫줄[0];q = 첫줄[1];deps = []; // deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례)best = []; // best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각반복 (i = 0; i < m; i++){ c = 콘솔.수들읽기()[0]; dep = 콘솔.수들읽기(); arr = 콘솔.수들읽기(); 반복 (j = 0; j < c; j++) { arr[j] = dep[j] + arr[j]; } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 목록이 되어 이분 탐색을 할 수 있다 반복 (j = c - 2; j >= 0; j--) { arr[j] = 수학.작은수(arr[j], arr[j + 1]); } deps.넣기(dep); best.넣기(arr);}반복 (k = 0; k < q; k++){ t = 콘솔.줄읽기().공백제거().나누기(); x = t[1].수로변환(); 만약 (t[0] == "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 반복 (i = 0; i < m; i++) { j = 첫자리이상(deps[i], x); 만약 (j == deps[i].개수) { x = -1; 그만; } x = best[i][j]; } } 아니면 { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 반복 (i = m - 1; i >= 0; i--) { j = 첫자리초과(best[i], x) - 1; 만약 (j < 0) { x = -1; 그만; } x = deps[i][j]; } } 콘솔.쓰기(x);}// a[j] >= x인 첫 자리(없으면 a.개수)첫자리이상(a, x){ lo = 0; hi = a.개수; 동안 (lo < hi) { mid = 수학.몫(lo + hi, 2); 만약 (a[mid] < x) { lo = mid + 1; } 아니면 { hi = mid; } } 돌려주기 lo;}// a[j] > x인 첫 자리(없으면 a.개수)첫자리초과(a, x){ lo = 0; hi = a.개수; 동안 (lo < hi) { mid = 수학.몫(lo + hi, 2); 만약 (a[mid] <= x) { lo = mid + 1; } 아니면 { hi = mid; } } 돌려주기 lo;}