BOJ 1187 : 숫자 놀이
2021. 8. 13. 01:34ㆍPS/Divide & Conquer
https://www.acmicpc.net/problem/1187
문제가 아주 좋으니 충분히 고민해보고 풀길 바란다.
먼저 이 문제에서 안되는 경우가 있는지 확인해보자.
일단 k=1일때는 비둘기집 원리에 의해 항상 답이 있다는 것을 알 수 있다.
그렇다면 여기서 귀납법을 이용해보자.
k = n-1일때 무조건 성립한다고 가정하자.
k = n일때, 2^(n+1)-1개의 원소가 있을것이며, 이를 2^(n-1)개의 원소가 들어가 있는 그룹 3개와 나머지 한개로 분리했다고 하자.
그렇다면 이 그룹 세 개 중 두 개를 합쳐 답을 구할 수 있는데, 이는 k=1에서와 같이 비둘기집의 원리가 성립되어 안되는 경우가 없음을 알 수 있다.
이를 바탕으로 풀이를 짜면,
분할 정복으로 크기가 2^k꼴인 같은 세개의 구간을 나눠서 이를 적절히 합하면 O(3^k)만에 풀 수 있다.