루미 알고리즘

#1119플래티넘가방가방

KOI 2025 2차코딩중등부 2번출제 구재현이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

가방

원제: 가방

문제

상훈이는 KOI 도시에서 상점을 운영하고 있는 시민이다. 상훈이의 상점은 NN개의 물건을 가지고 있으며, 이 중 ii번째 물건의 무게는 AiA_i이다. 상훈이는 도둑 김기범이 본인의 상점을 노리고 있다는 첩보를 들었고, 이에 대비해 피해를 최소화하려고 한다.

도둑 김기범은 가게에서 KK개의 물건을 훔쳐갈 것인데, 물건이 무거울 경우 훔쳐가기 어렵고 경찰한테 걸릴 가능성이 높다. 고로, 도둑 김기범은 훔쳐가는 물건의 무게의 합을 최소화한다. 만약 가게에 있는 물건의 개수가 KK개 미만일 경우, 도둑 김기범은 가게에 있는 모든 물건을 훔쳐간다.

상훈이는 도둑 김기범이 가게를 도착하기 전에, 가방에 상점의 물건들을 몇 개 담아서 들고 갈 것이다. 이후, 도둑 김기범은 상훈이가 들고 가지 않은 물건들에 대해 위에 설명한 방식으로 범죄를 저지른다. 상훈이는 가방에 물건을 적당히 담아서 도둑 김기범이 훔쳐가는 물건의 무게 합을 최대화하려고 한다.

상훈이의 가방이 감당할 수 있는 무게는 한정되어 있다. 입력으로 최댓값 CC가 주어졌을 때, 모든 x=1,2,…,Cx = 1, 2, \ldots, C에 대해 다음 질문에 답하라:

  • 상훈이가 가방에 담을 수 있는 물건들의 무게 합이 xx 이하여야 한다는 조건하에, 도둑 김기범이 훔쳐가는 물건들의 무게 합의 최댓값은 얼마인가?

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤K≤N≤5 0001 \le K \le N \le 5\,000
  • 1≤C≤1 000 0001 \le C \le 1\,000\,000
  • 모든 ii (1≤i≤N1 \le i \le N) 에 대해 1≤Ai≤1 000 0001 \le A_i \le 1\,000\,000

부분문제

  1. (13점) N≤10,Ai≤10 000,C≤10 000N \le 10, A_i \le 10\,000, C \le 10\,000
  2. (17점) N≤80,Ai≤10 000,C≤10 000N \le 80, A_i \le 10\,000, C \le 10\,000
  3. (23점) Ai≤10 000,C≤10 000A_i \le 10\,000, C \le 10\,000
  4. (16점) K=1K = 1
  5. (31점) 추가 제약 조건 없음

입력 형식

첫 번째 줄에 N,K,CN, K, C가 공백으로 구분되어 주어진다.

두 번째 줄에 NN 개의 정수 A1,A2,…,ANA_1, A_2, \ldots, A_N이 공백으로 구분되어 주어진다.

출력 형식

CC 개의 줄을 출력한다. ii 번째 줄에는, x=ix = i일 때 도둑 김기범이 훔쳐가는 물건들의 무게 합의 최댓값을 출력한다.

예제

예제 1

입력
5 1 6
1 2 3 4 5
출력
2
2
3
3
3
4

예제 2

입력
5 2 5
2 3 5 7 11
출력
5
8
8
8
12

예제 3

입력
3 2 3
1 1 7
출력
8
8
8

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.