ps:problems:boj:1659
수 (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)
코드
- 다이아몬드 이상은 코드 생략
ps/problems/boj/1659.txt · 마지막으로 수정됨: 2026/02/11 09:14 저자 teferi
토론