BOJ 10350 은행 (IMO 1986)

https://www.acmicpc.net/problem/10350

10350번: 은행

지금 까지 풀어본 문제 중 체감 난이도가 가장 어려운 문제 중 하나이다.

1986년 국제수학올림피아드 (IMO 1986) 3번 문제의 일반화 버전으로, 당장 IMO 1986에서도 3번 문제가 가장 어려웠다는 평가가 있다. 그런 문제의 일반화 버전이니 문제의 난이도는 더 말할 필요가 없다.

SEERC 2014의 A번 문제로도 출제되었다. (이 문제가 A라고?!).
대회 사이트에서 테스트 인풋 아웃풋을 받아서 보았는데, 테스트 데이터가 굉장히 빈약한 편, 따라서 아주 naive하게 구현해도 AC를 받을 수 있었을 듯하다. (데이터를 이렇게 부실하게 출제하면 안 된다. 문제를 대충 푼 팀은 맞고, 진지하게 고민한 팀만 문제에 손도 못 대고 손해 본다.)

문제의 해법은 책 Problem Solving-Strategies의 1장 E9에서 다뤘다.
(책 링크: https://link.springer.com/book/10.1007/b97682)

책에서 설명한 문제의 해법을 일반화하면,

우선 주어진 수를 무한히 반복하는 수열을 생각해볼 수 있다. x_1, x_2, ..., x_n, x_n+1 (= x_1), x_n+2 (=x_2), ...
무한한 구간합의 집합 s(i ,j) = x_i + x_i+1 + x_i+2 + .... + x_j-1 (1 < i <= n, j > i) 를 생각해 볼 수 있다.
위 구간합의 집합에서 값이 음수인 것만 고려하면, 값이 음수인 집합은 유한개이다. (x_1 + x_2 + ... + x_n > 0 이므로)

이제 주어진 숫자 중 값이 음수인 것을 아무거나 하나 골라서 변환을 하는 과정을 생각해보자. (아래에서 양수는 0을 포함)

x_k < 0 이라고 했을 때,

• s(k, k+1) 에 대해서
  • s(k, k+1)  -> 음수에서 양수로 바뀐다.
  • 음수인 구간합 s의 개수가 하나 줄어든다.
• s(k-1, k), s(k-1, k+1)에 대해서
  • x_k-1 이 음수인 경우,
    • s(k-1, k) -> 음수에서 음수로 유지된다.
    • s(k-1, k+1)  -> 음수에서 음수로 유지된다.
    • 음수인 구간합 s의 개수는 불변
  • x_k-1 이 양수이고 |x_k-1| >= |x_k| 인 경우,
    • s(k-1, k) -> 양수에서 양수로 유지된다.
    • s(k-1, k+1) ->  양수에서 양수로 유지된다.
    • 음수인 구간합 s의 개수는 불변
  • x_k-1 이 양수이고 |x_k-1| < |x_k| 인 경우,
    • s(k-1, k) -> 양수에서 음수로 바뀐다.
    • s(k-1, k+1) -> 음수에서 양수로 바뀐다.
    • 음수인 구간합 s의 개수는 불변
• s(k, k+2), s(k+1, k+2)에 대해서도 동일
• k-1, k, k+1 을 포함하는 구간합은 그 합이 변하지 않는다. 따라서 음수인 구간합 집합의 개수는 유지됨.

따라서 x_k < 0 인 어떤 k를 선택해서 연산을 하더라도 음수인 구간합의 집합 s(i ,j) 는 한 개 줄어든다는 것을 알 수 있다. 앞서 음수인 구간합의 집합은 유한개이기 때문에, 알고리즘은 종료함을 알 수 있다.

결론

• 순서에 상관없이 아무거나 음수인 숫자를 골라서 주어진 연산을 하면, 최적의 횟수로 알고리즘이 종료한다.
• 연산 수행 횟수는 구간합의 집합 s(i, j) 중 합이 음수인 구간합의 개수와 동일하다.

 

문제의 해법을 알고 나서 이해하는 난이도 자체는 그렇게 어렵지는 않다. 그럼에도 이 문제가 체감상 가장 어려운 문제로 느껴지는 이유는, 문제 자체가 근본이 없고(무족보), 증명 과정이 꽤 생소했기 때문(무한한 구간합의 집합..). 족보가 있는 문제는 그 문제나 족보(자료구조, 증명, 알고리즘 등)가 아무리 어렵더라도, 미리 공부를 해서 몸에 익혀둘 수 있지만, 이런 문제는 선행학습이 거의 불가능하다. 이런 문제를 대회장에서 만나면, 먼치킨 급 천재이거나 이전에 문제를 접해보지 않은 이상, 즉석에서 문제를 분석하고 증명하고 해결하는 것은 거의 불가능에 가까울 것 같다. (나는 못 푼다.)