[알고리즘 문제 풀이][슬라이딩윈도우] 백준 16440번 - 제이크와 케이크

백준 16440번 제이크와 케이크 문제입니다.

(슬라이딩 윈도우)

 

- 문제 설명: https://www.acmicpc.net/problem/16440

- 문제 풀이:

 

본 문제는 Necklace splitting problem 이라고 치면 나오는 위상 수학의 유명한 문제와 같습니다. 두 도둑이 하나의 목걸이를 반으로 나눠 가지려고 하는데 목걸이에 있는 보석들을 종류마다 똑같은 개수로 나눠갖도록 하는 것입니다. 그때 자르는 횟수를 최소한으로 해야합니다. 이 문제는 위상 수학의 보르수크-울람 정리 (Borsuk-Ulam theorem) 으로 증명이 되었는데, 위상 수학에 대해 이해할 수 있다면 아래 동영상으로 증명 과정을 따라가 볼 수 있습니다.

https://www.youtube.com/watch?v=yuVqxCSsE7c 

위의 영상을 이해하지 못하더라도 결론부터 말하자면, 이미 증명이 된 것으로 보석의 종류 (본 문제로 따지면 케이크 위의 과일의 종류) n 개가 있다면 최대 n 컷이면 무조건 절반으로 나눌 수 있습니다. 그러면 제이크와 케이크 문제에서는 과일이 2개 (딸기와 키위) 이므로 최대 2번만 자르면 두 명이 딸기와 키위의 개수를 똑같이 나눠 가질 수 있습니다.

그러므로 문제의 답은 무조건 1번 혹은 2번이 되는 것입니다. 1번 자르는 경우는 무조건 중앙을 자르는 경우입니다. 그렇지 않다면 슬라이딩 윈도우로 옆으로 보면서 어느 지점의 앞 뒤로 자르면 개수가 같아지는지 보면 됩니다.

 

제가 작성한 코드는 아래와 같습니다.

 

- 코드: 

N = int(input())
cake = input()
s = 0
for i in range(N//2):
    if cake[i] == 's':
        s += 1

if s == N//4:
    print(1)
    print(N//2)
else:
    for i in range(N//2):
        if cake[i] == 's':
            s -= 1
        if cake[i+N//2] == 's':
            s += 1
        if s == N//4:
            print(2)
            print(i+1, i+N//2+1)
            break

 

 

- 실수 포인트 & 반례:

1. 최대 2 컷이지만 그것이 잘 고려되지 않은 경우, 틀린 답이 나올 수 있습니다.

https://www.acmicpc.net/board/view/35001

입력)
8
skkksssk
정답)
2
2 6

 

※ 위상 수학으로 증명하지 않는 방법

- f(x) 를 x 부터 x + n/2 까지에서의 딸기의 수라고 정의하면 f(0) 이 n/4 보다 크다면 f(n/2) 는 반드시 n/4 보다 작다. f(x) 와 f(x+1) 은 최대 1 차이가 나기 때문에, 미적에서의 중간값 정리와 같이 f(k) = n/4 인 k 가 반드시 존재한다는 귀류법이 가능할 것이다. (조언을 받았으나 아직 실제로 만들어보진 못함)

 

- 케이크의 앞 절반이 만약 딸기의 개수가 n/4 개보다 많이 있다면, 뒤의 절반은 n/4 보다 적게 있을 것이다. 옆으로 슬라이딩 윈도우를 하나씩 밀어간다면, 개수가 1개씩 늘거나 줄거나 하면서 마지막에는 n/4 보다 적어져야하므로, 어느 지점에서는 반드시 n/4 인 지점을 지날 수밖에 없다!!