수 (Hard)

ps
링크	acmicpc.net/…
출처	BOJ
문제 번호	1659
문제명	수 (Hard)
레벨	다이아몬드 1
분류	DP
시간복잡도	O(n+m)
인풋사이즈	n<=500,000, m<=500,000
사용한 언어	Python 3.13
제출기록	243448KB / 1308ms
최고기록	1308ms
해결날짜	2026/02/11

풀이

1628에서 제한을 늘린 문제이다. 대회(2007 ICPC 서울예선) 에서 출제되었던 원본 문제은 제한이 작은 버전이었고, 거기에서는 O(n^2)으로도 통과가 가능했으나, 이 문제에서는 O(n) 알고리즘이 필요하다
cubelover 블로그에 이 문제의 풀이가 있었는데 지금은 블로그가 삭제되었다. 웹 아카이브에 저장된 글이 있다
이 문제와 동일한 문제(20077)가 IOI 2017 에 출제되었다. 풀이를 찾는다면, 이 문제의 풀이를 찾아서 똑같이 적용하는 것이 더 쉬울 것이다. (20년전 한국대회 문제 vs 10년전 세계대회 문제)
나도 풀이를 보고 풀긴 했지만, 모든 스텝을 완전히 명쾌하게 이해한 느낌은 아니다..; 비슷한 문제를 접했을때 풀수 있을지 잘 모르겠다.
그것과 별개로 cubelover의 풀이에서 (너무 간단하다고 생각해서?) 설명 안하고 넘어간 부분들을 보충하면
- j+1~i번째 원소 중 S에 속하는 원소의 개수와 T에 속하는 원소의 개수가 같은 최대의 j를 찾고 그 원소들 간의 최소 매칭 비용을 O(1)에 구하는 방법은 다음과 같다.
  - i번째 원소까지의 {S에 속하는 원소의 개수} - {T에 속하는 원소의 개수} 를 계산한다.
  - i번째 원소에 대해서 구한 이 값이, j번째 원소에 대해서 구한 값과 같다면, j번째~i번째 원소들은 S에 속하는 원소와 T에 속하는 원소의 개수가 같다
  - 그러므로, 원소개수의 차이가 x인 가장 큰 인덱스를 저장해두면, j+1~i번째 원소 중 S에 속하는 원소의 개수와 T에 속하는 원소의 개수가 같은 최대의 j를 O(1)에 구할수 있다.
  - j+1~i번째 원소에 대해서 |(S에 속하는 원소들의 합)-(T에 속하는 원소들의 합)| 을 구하는 것은 누적합을 이용해서 O(1)에 구할수 있다.
시간복잡도는 O(n)

코드

다이아몬드 이상은 코드 생략

BOJ, 다이아몬드 1

목차

수 (Hard)

풀이

코드