테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 수 (Hard) ======

===== 풀이 =====
  * [[ps:problems:boj:1628]]에서 제한을 늘린 문제이다. 대회(2007 ICPC 서울예선) 에서 출제되었던 원본 문제은 제한이 작은 버전이었고, 거기에서는 O(n^2)으로도 통과가 가능했으나, 이 문제에서는 O(n) 알고리즘이 필요하다
  * cubelover 블로그에 이 문제의 풀이가 있었는데 지금은 블로그가 삭제되었다. 웹 아카이브에  [[https://web.archive.org/web/20170809115317/https://cubelover.tistory.com/8|저장된 글]]이 있다
  * 이 문제와 동일한 문제([[ps:problems:boj: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)

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

{{tag>BOJ ps:problems:boj:다이아몬드_1}}