파일 n개가 1번부터 n번까지 차례로 있고, i번 파일의 크기는 wᵢ다. 이 파일들을 용량이 모두 C인 백업 디스크 여러 장에 번호 차례대로 나눠 담는다. 디스크 한 장에는 번호가 이어진 파일들만 담고, 한 장에 담은 파일 크기의 합은 C를 넘을 수 없다. 파일의 차례를 바꾸거나 한 파일을 두 장에 나눠 담을 수는 없다. 디스크를 d장 이하로 써서 모든 파일을 담을 수 있는 가장 작은 정수 C를 출력하라. 첫 줄에 n과 d가, 둘째 줄에 w₁ … wₙ이 빈칸으로 나뉘어 주어진다.
6 3 3 2 2 4 1 4
6
4 2 1 1 1 10
10
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
C를 1부터 하나씩 늘려 보면 합(10¹³)까지 가야 할 수도 있어요.
용량이 클수록 필요한 디스크는 줄어드니 'd장 이하로 되는가'는 앞쪽이 거짓, 뒤쪽이 참이에요.
그래서 답을 이분 탐색해요: 가운데 mid로 디스크가 몇 장 필요한지 세어 보고, 되면 hi = mid, 안 되면 lo = mid + 1.
장 수 세기는 욕심쟁이예요 — 지금 디스크에 더 들어가면 담고, 넘치면 새 디스크로 넘어가요.
많아야 44번 × n이라 금방 끝나요.
함정 셋: ① 아래 끝은 1이 아니라 가장 큰 파일이에요.
1부터 찾으면 장 수 세기가 들어가지 않는 파일도 그 디스크에 담아 버려서, 예시 2처럼 10보다 작은 답이 나와요.
② 합은 10¹³까지라 Java·C#·C·C++에서 long/long long이어야 해요.
C#의 w.Sum()은 int로 더하다가 OverflowException을 내니 w.Sum(x => (long)x), C++ std::accumulate는 시작값을 0LL로 줘야 long long으로 더해요.
Python은 넘치지 않고, JavaScript·TypeScript·크레이콘은 수가 double이라 2^53(약 9×10¹⁵) 안이면 정확해요.
③ 장 수는 1부터 세요 — 0부터 세면 지금 담고 있는 마지막 디스크를 빠뜨려요.
크레이콘은 정수 나눗셈이 없어서 가운데를 수학.몫(lo + hi, 2)로 구해요.
def disks_needed(w, cap): """용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).""" disks, used = 1, 0 for x in w: if used + x > cap: disks += 1 used = 0 used += x return disks n, d = map(int, input().split())w = list(map(int, input().split())) # 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이. '되는가'는 앞쪽이 거짓, 뒤쪽이 참이다.lo, hi = max(w), sum(w)while lo < hi: mid = (lo + hi) // 2 if disks_needed(w, mid) <= d: hi = mid else: lo = mid + 1print(lo)// 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).function disksNeeded(w, cap) { let disks = 1; let used = 0; for (const x of w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks;} const [n, d, ...w] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이. 합은 10¹³까지라 2^53 안이다.let lo = Math.max(...w);let hi = w.reduce((s, x) => s + x, 0);while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1;}console.log(lo);import { readFileSync } from "node:fs"; // 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).function disksNeeded(w: number[], cap: number): number { let disks = 1; let used = 0; for (const x of w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks;} const [n, d, ...w]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이. 합은 10¹³까지라 2^53 안이다.let lo = Math.max(...w);let hi = w.reduce((s, x) => s + x, 0);while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1;}console.log(lo);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { // 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일). static int disksNeeded(int[] w, long cap) { int disks = 1; long used = 0; for (int x : w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int d = Integer.parseInt(st.nextToken()); int[] w = new int[n]; long lo = 0, hi = 0; // 합은 10¹³까지라 long st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { w[i] = Integer.parseInt(st.nextToken()); lo = Math.max(lo, w[i]); hi += w[i]; } while (lo < hi) { long mid = lo + (hi - lo) / 2; if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1; } System.out.println(lo); }}using System;using System.Linq; class Program{ // 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일). static int DisksNeeded(int[] w, long cap) { int disks = 1; long used = 0; foreach (int x in w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks; } static void Main() { int d = int.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[1]); int[] w = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); long lo = w.Max(); long hi = w.Sum(x => (long)x); // w.Sum()은 int로 더하다 OverflowException while (lo < hi) { long mid = lo + (hi - lo) / 2; if (DisksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1; } Console.WriteLine(lo); }}#include <algorithm>#include <iostream>#include <numeric>#include <vector> // 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).int disksNeeded(const std::vector<int>& w, long long cap) { int disks = 1; long long used = 0; for (int x : w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks;} int main() { int n, d; std::cin >> n >> d; std::vector<int> w(n); for (int& x : w) std::cin >> x; long long lo = *std::max_element(w.begin(), w.end()); long long hi = std::accumulate(w.begin(), w.end(), 0LL); // 0이 아니라 0LL: 시작값의 타입으로 더한다 while (lo < hi) { long long mid = lo + (hi - lo) / 2; if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1; } std::cout << lo << "\n";}#include <stdio.h> static int w[10000]; /* 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일). */static int disks_needed(int n, long long cap) { int disks = 1; long long used = 0; for (int i = 0; i < n; i++) { if (used + w[i] > cap) { disks++; used = 0; } used += w[i]; } return disks;} int main(void) { int n, d; long long lo = 0, hi = 0; /* 합은 10¹³까지라 long long */ scanf("%d %d", &n, &d); for (int i = 0; i < n; i++) { scanf("%d", &w[i]); if (w[i] > lo) lo = w[i]; hi += w[i]; } while (lo < hi) { long long mid = lo + (hi - lo) / 2; if (disks_needed(n, mid) <= d) hi = mid; else lo = mid + 1; } printf("%lld\n", lo); return 0;}// 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).필요한디스크(w, cap){ disks = 1; used = 0; 각각 (x 에서 w) { 만약 (used + x > cap) { disks += 1; used = 0; } used += x; } 돌려주기 disks;} 첫줄 = 콘솔.수들읽기();d = 첫줄[1];w = 콘솔.수들읽기();// 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이lo = 0;hi = 0;각각 (x 에서 w){ lo = 수학.큰수(lo, x); hi += x;}동안 (lo < hi){ mid = 수학.몫(lo + hi, 2); 만약 (필요한디스크(w, mid) <= d) { hi = mid; } 아니면 { lo = mid + 1; }}콘솔.쓰기(lo);