루미 알고리즘

#1122플래티넘상자 보관상자 보관

KOI 2025 2차코딩초등부 4번출제 반딧불이 문제가 어렵다면 — 배우는 순서 보기

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

상자 보관

원제: 상자 보관

문제

정올이는 창고에 상자를 보관하려고 한다. 상자는 총 NN개가 있으며 11부터 NN까지의 번호가 붙어 있다. ii (1≤i≤N1 \le i \le N)번 상자의 크기는 sis_i, 보관 용량은 cic_i이다. 모든 상자는 보관 용량이 그 크기보다 작다. 즉, ci<sic_i < s_i를 만족한다.

창고에 상자가 너무 많아 복잡하다고 생각한 정올이는, 상자를 다른 상자의 안에 넣어서 보관하고자 한다. 이때, 다음과 같은 조건이 만족되어야 한다.

  • 한 상자에는 해당 상자의 보관 용량 이하의 크기를 갖는 상자를 넣을 수 있다.
  • 이미 상자를 포함한 상자를 다른 상자 안에 넣는 것도 가능하다.
  • 한 상자에 직접 포함되는 상자는 최대 하나여야 한다. 다시 말해, 한 상자 안에는 다른 상자를 최대 하나 넣을 수 있지만, 그 다른 상자 안에 또 다른 상자들이 들어가 있는 것은 허용된다.

상자를 보관하는 비용은 다른 상자에 포함되지 않은 상자의 개수와 같다.

예를 들어, N=4N = 4이고, 네 상자의 크기와 보관 용량이 각각 아래 표와 같은 경우를 생각하자.

번호크기보관 용량
116644
225511
339988
442211

이때, 아래 그림처럼 44번 상자를 11번 상자에 넣고, 11번 상자를 33번 상자에 넣으면, 다른 상자에 포함되지 않은 상자의 수는 22개가 되고, 따라서 상자를 보관하는 비용은 22가 된다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

그러나 아래 그림처럼 22번 상자와 44번 상자를 33번 상자에 넣는 경우, 33번 상자 안에 두 개의 상자가 직접 포함되어 있으므로, 조건을 만족하지 않는다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

창고에 반드시 모든 상자를 둘 필요는 없어서, 정올이는 번호가 작은 몇 개의 상자만 보관하고 나머지 상자는 버릴 계획을 하고 있다. 정올이는 아직 몇 개의 상자를 사용할지는 정하지 못한 상태이다.

정올이를 도와, 11부터 NN까지의 모든 ii에 대해, 1,2,…,i1, 2, \ldots, i번 상자를 보관하는 데 드는 최소 비용을 계산하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 2≤N≤2×1052 \le N \le 2 \times 10^5
  • 1≤ci<si≤1091 \le c_i < s_i \le 10^9 (1≤i≤N)(1 \le i \le N)

부분문제

  1. (7점) N≤6N \le 6.
  2. (12점) si=ci+1s_i = c_i + 1.
  3. (26점) N≤1000N \le 1000.
  4. (17점) si≤100s_i \le 100.
  5. (38점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에는 상자의 수 NN이 주어진다.

두 번째 줄부터 NN개의 줄에 걸쳐 각 상자의 정보가 주어진다. 이 중 ii번째 줄에는 ii번 상자의 크기 sis_i와 보관 용량 cic_i가 공백을 사이에 두고 주어진다.

출력 형식

NN개의 줄을 출력한다.

ii (1≤i≤N1 \le i \le N)번째 줄에는 1,2,…,i1, 2, \ldots, i번 상자를 보관하는 데 드는 최소 비용을 출력한다.

예제

예제 1

입력
4
6 4
5 1
9 8
2 1
출력
1
2
2
2

예제 2

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

예제 3

입력
8
13 6
7 5
9 4
11 10
4 2
15 5
16 7
8 3
출력
1
2
3
3
3
4
4
5

자료

출처 표기

출처: 한국정보올림피아드(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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.