[CodeJam][2017] Bathroom Stalls - Qualification Round C

문제 : https://code.google.com/codejam/contest/3264486/dashboard#s=p2

---

N이 9라고 할 때를 예로 들어보자.

파란색이 연속된 빈 자리(탐색 중인 자리들). 빨간 색이 이때 선택되는 최적의 자리이다.

연속된 빈 자리가 많을 수록 우선으로 선택된다. (최대, 최소가 크므로)

그리고 연속된 빈 자리수가 같다면 구하고자 하는 다른 상점 or 화장실과의 최대, 최소 거리는 같다. -> 한꺼번에 계산할 수 있다.

map을 하나 만든다. key 값은 연속된 빈 자리이고 value는 연속된 빈 자리 수의 개수가 된다.

key 값이 큰 것부터 탐색한다. (거리의 최대, 최소는 연속된 빈 자리 수에 비례하므로)

탐색중인 map의 key값을 n, value를 cnt라 하자.

cnt만큼의 자리들을 한 번에 정할 수 있고 그 자리의 최대, 최소 거리는 n/2, (n-1)/2 이다.

최대 최소 거리가 n/2, (n-1)/2가 되는 이유는 위 그림과 같다. 연속된 자리 수 n이 짝수, 홀수일때 최대, 최소 거리가 달라질 수 있는데 이를 일반화 하면 n/2, (n-1)/2가 된다.

cnt 만큼의 자리들이 정해지면 n/2, (n-1)/2 의 연속된 자리 수들이 각각 cnt만큼 생긴다.

이를 다시 map에 저장한다.

이를 반복하면서 K번째 자리일 때 다른 상점 or 화장실과의 최대, 최소 거리를 구할 수 있다.

이 해답을 분할 정복 이라고 봐도 되겠..지...?

---

소스코드 : https://gist.github.com/fpdjsns/403eaec4e97d1fae08afc99142952b07