능선을 따라 등산로 구간 n개가 한 줄로 이어져 있고, 1번부터 n번까지 번호가 붙어 있다.
i번 구간을 걸으면 힘이 aᵢ만큼 든다.
등산객은 이어진 구간 l번부터 r번까지(1 ≤ l ≤ r ≤ n)를 골라 '길'로 삼는다.
길 안에서 힘이 가장 많이 드는 구간 하나는 케이블카를 타고 지나가서 힘이 들지 않는다. 힘이 가장 많이 드는 구간이 여러 개여도 케이블카는 한 구간만 탄다.
나머지 구간에 드는 힘의 합이 T 이하이면 그 길은 '걸을 만한 길'이다.
구간이 하나뿐인 길은 드는 힘이 0이라 언제나 걸을 만한 길이다.
첫 줄에 걸을 만한 길 (l, r)의 개수를 출력하라.
둘째 줄에 걸을 만한 길 가운데 구간 수가 가장 많은 길의 구간 수와 시작 번호 l을 출력하라. 그런 길이 여러 개이면 l이 가장 작은 것을 고른다.
입력
첫 줄에 n과 T, 둘째 줄에 a₁ … aₙ이 빈칸 하나로 나뉘어 주어진다. 1 ≤ n ≤ 10,000, 0 ≤ T ≤ 10,000,000,000,000(10^13), 1 ≤ aᵢ ≤ 1,000,000,000. 모두 정수다
출력
두 줄: 첫 줄에 걸을 만한 길의 개수, 둘째 줄에 가장 긴 길의 구간 수와 시작 번호를 빈칸 하나로 띄워 출력한다. 쉼표 없이 숫자만 쓴다
예시 1 · stdin
6 5
3 9 2 4 1 7
stdout
14
3 1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
길을 오른쪽으로 한 칸 늘리면 '합 − 최댓값'은 줄지 않아요(새 구간이 최댓값보다 작으면 그만큼 늘고, 크면 옛 최댓값만큼 늘어요). 그래서 오른쪽 끝 r을 한 칸씩 옮기고 왼쪽 끝 l은 넘칠 때만 앞으로 옮기는 두 포인터로 풀 수 있고, r에서 끝나는 걸을 만한 길은 r − l + 1개예요. 창 안의 최댓값은 매번 다시 찾으면 n²이니 덱에 '아직 최댓값이 될 수 있는 자리'만 큰 것부터 남겨요: 새 구간보다 작거나 같은 뒤쪽 후보를 빼고 넣고, 왼쪽 끝이 지나간 후보는 앞에서 빼요. 예시: T = 5일 때 9 2 4는 9를 케이블카로 넘어 2 + 4 = 6이라 안 되고, 2 4 1은 2 + 1 = 3이라 돼요. 함정 하나: 합만 보고 합 ≤ T로 창을 움직이면(케이블카를 잊으면) 틀려요. 함정 둘: 넘칠 때 if로 한 번만 줄이면 가장 긴 길이는 맞을 수 있어도 개수가 틀려요 — while이에요. 함정 셋: 왼쪽 끝이 지나간 자리를 덱 앞에서 빼지 않으면 이미 창을 나간 큰 구간을 계속 빼 줘요. 함정 넷: 지금 최댓값보다 작은 구간을 후보에서 버리면, 최댓값이 창을 나간 뒤 다음 최댓값을 몰라요. 함정 다섯: 길이가 같을 때 >=로 바꾸면 시작이 뒤인 길이 남아요. 함정 여섯: 합은 10^13까지 가니 C·C++은 long long, Java·C#은 long이에요(32비트 int는 약 21억까지). Python 정수는 넘치지 않고, JavaScript·TypeScript·크레이콘의 수는 2^53(약 9×10^15)까지 정확해요. 덱은 언어마다 달라요: Python collections.deque, Java ArrayDeque, C++ std::deque가 있고, C#에는 덱 클래스가 없어 배열과 머리·꼬리 번호로 만들어요(C도 같아요). JavaScript·TypeScript 배열의 shift()와 크레이콘 목록의 자리빼기(0)은 뒤의 것을 모두 당기니, 앞에서 뺄 때는 머리 번호(head)만 하나 올려요.
Pythonmain.py · 31 줄
import sysfrom collections import dequedata = sys.stdin.buffer.read().split()n, limit = int(data[0]), int(data[1])a = [int(x) for x in data[2:2 + n]]dq = deque() # 창 안에서 '가장 힘든 구간' 후보의 자리. 힘이 큰 것부터 작은 것 순서로 남는다left = 0total = 0 # 창 안의 힘의 합count = 0best_len = 0best_start = 0for right in range(n): total += a[right] while dq and a[dq[-1]] <= a[right]: dq.pop() dq.append(right) # 가장 힘든 구간(dq[0])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while total - a[dq[0]] > limit: total -= a[left] if dq[0] == left: dq.popleft() left += 1 length = right - left + 1 count += length # right에서 끝나는 길은 시작이 left..right인 것 모두 if length > best_len: # 같으면 먼저 찾은(시작이 앞선) 것을 둔다 best_len = length best_start = left + 1print(count)print(best_len, best_start)
JavaScriptmain.js · 32 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const limit = data[1];const a = data.slice(2, 2 + n);// 덱: 배열 하나와 머리 번호. shift()는 뒤의 것을 모두 당기니 쓰지 않는다const dq = new Array(n);let head = 0;let tail = 0; // dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터)let left = 0;let total = 0;let count = 0;let bestLen = 0;let bestStart = 0;for (let right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] === left) head++; left++; } const length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; }}console.log(count + "\n" + bestLen + " " + bestStart);
TypeScriptmain.ts · 34 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n: number = data[0];const limit: number = data[1];const a: number[] = data.slice(2, 2 + n);// 덱: 배열 하나와 머리 번호. shift()는 뒤의 것을 모두 당기니 쓰지 않는다const dq: number[] = new Array<number>(n).fill(0);let head = 0;let tail = 0; // dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터)let left = 0;let total = 0;let count = 0;let bestLen = 0;let bestStart = 0;for (let right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] === left) head++; left++; } const length: number = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; }}console.log(`${count}\n${bestLen} ${bestStart}`);
JavaMain.java · 39 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); long limit = Long.parseLong(st.nextToken()); long[] a = new long[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken()); // 창 안에서 '가장 힘든 구간' 후보의 자리. 힘이 큰 것부터 작은 것 순서로 남는다 ArrayDeque<Integer> dq = new ArrayDeque<>(); int left = 0, bestLen = 0, bestStart = 0; long total = 0; // 10^13까지 가서 int로는 넘친다 long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (!dq.isEmpty() && a[dq.peekLast()] <= a[right]) dq.pollLast(); dq.addLast(right); // 가장 힘든 구간(맨 앞)은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq.peekFirst()] > limit) { total -= a[left]; if (dq.peekFirst() == left) dq.pollFirst(); left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } System.out.println(count); System.out.println(bestLen + " " + bestStart); }}
C#Main.cs · 42 줄
using System;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]); long limit = long.Parse(data[1]); var a = new long[n]; for (int i = 0; i < n; i++) a[i] = long.Parse(data[2 + i]); // .NET에는 Deque 클래스가 없다: 배열 하나와 머리·꼬리 번호로 덱을 만든다 var dq = new int[n]; int head = 0, tail = 0; // dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터) int left = 0, bestLen = 0, bestStart = 0; long total = 0; // 10^13까지 가서 int로는 넘친다 long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] == left) head++; left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } Console.WriteLine(count); Console.WriteLine($"{bestLen} {bestStart}"); }}
C++main.cpp · 38 줄
#include <deque>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long limit; cin >> n >> limit; vector<long long> a(n); for (auto &x : a) cin >> x; deque<int> dq; // 창 안에서 '가장 힘든 구간' 후보의 자리. 힘이 큰 것부터 작은 것 순서로 남는다 int left = 0, bestLen = 0, bestStart = 0; long long total = 0; // 10^13까지 가서 int로는 넘친다 long long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (!dq.empty() && a[dq.back()] <= a[right]) dq.pop_back(); dq.push_back(right); // 가장 힘든 구간(dq.front())은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq.front()] > limit) { total -= a[left]; if (dq.front() == left) dq.pop_front(); left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } cout << count << "\n" << bestLen << " " << bestStart << "\n"; return 0;}
Cmain.c · 36 줄
#include <stdio.h>#define MAXN 10000static long long a[MAXN];static int dq[MAXN]; /* 덱: dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터) */int main(void) { int n; long long limit; if (scanf("%d %lld", &n, &limit) != 2) return 1; for (int i = 0; i < n; i++) scanf("%lld", &a[i]); int head = 0, tail = 0, left = 0, bestLen = 0, bestStart = 0; long long total = 0; /* 10^13까지 가서 int로는 넘친다 */ long long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; /* 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 */ while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] == left) head++; left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } printf("%lld\n%d %d\n", count, bestLen, bestStart); return 0;}
Craykonmain.cray · 41 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];limit = 첫줄[1];a = 콘솔.수들읽기();// 덱: 목록 하나와 머리 번호. 자리빼기(0)은 뒤의 것을 모두 당기니 머리 번호만 옮긴다dq = [];head = 0; // dq[head..]가 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터)left = 0;total = 0;count = 0;bestLen = 0;bestStart = 0;반복 (right = 0; right < n; right++){ total += a[right]; 동안 (dq.개수 > head && a[dq[dq.개수 - 1]] <= a[right]) { dq.자리빼기(dq.개수 - 1); } dq.넣기(right); // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 동안 (total - a[dq[head]] > limit) { total -= a[left]; 만약 (dq[head] == left) { head += 1; } left += 1; } length = right - left + 1; count += length; 만약 (length > bestLen) { bestLen = length; bestStart = left + 1; }}콘솔.쓰기(count);콘솔.쓰기(bestLen + " " + bestStart);