문제를 간단히 요약하자면, 특정 구간과 그 내부에 있는 표시의 개수가 여러개 주어졌을 때 이를 만족하는 해를 아무거나 출력하거나, 혹은 그러한 것이 존재하지 않는다고 출력하는 것이다. 해당 문제는 한국정보올림피아드 기출문제로, 일반적으로 그래프 이론의 알고리즘들을 사용하여 해결할 수 있는 것으로 알려져있다. 그러나, 해당 글에서는 정풀이와는 조금 다른 방법으로 문제를 해결하였다.
우선, n의 크기가 매우 작다는 것을 관찰하자. 만약 n이 20정도로 충분히 작았다면 브루트포스 알고리즘을 통해 해를 찾기만 하면 충분했을 것이다. n이 이보다 조금 더 클때, 즉 약 40정도일 때 브루트포스 알고리즘을 사용하기 위해 주로 사용하는 것은 meet in the middle 기법인데, 이는 즉 문제를 절반으로 쪼개어 각각에 대해 브루트포스를 적용하고 계산함으로써 시간복잡도를 루트만큼 줄이는 것이다.
만약 이렇게 구간 전체를 절반으로 나눈 다음 각 구간에 대한 완전탐색을 진행하면 시간복잡도는 적절할 것이다. 이제 왼쪽 구간에 대해 대응되는 오른쪽 구간을 찾아야 하는데, 이것은 해싱을 통해 처리 가능하다. 각 구간에 대해, 넉넉잡아 50진법, 51진법을 통해 총 몇개의 표시가 존재하는지를 나타내자. 예를 들어, 첫 구간이 [1,6]이고, 두번째 구간이 [2,4]였다면 50*2+1*1로 나타날 것이다. 만약 이런 표시와 그에 대한 표현을 전부 저장해둔다면, 우리가 원하는 조건의 수에서 왼쪽 구간이 나타내는 수를 뺀 것이 오른쪽 구간중에 존재하는지를 확인하면 충분하다. 저 매우 큰 수는 적절한 소수들에 대해서 법을 취하고, map을 사용하여 해싱을 사용한다. 즉, 각 표현이 중첩될 가능성은 매우 적다는 것이다.
위의 논리를 그대로 구현하면 된다. 따라서 전체 시간복잡도는 O(2^(n/2)*n)정도...이다. 다만 메모리 제한과 시간제한이 상당히 빡빡하기 때문에 구현시 유의해야 한다.
'사풀이' 카테고리의 다른 글
백준 19702 - 친구 (1) | 2022.12.20 |
---|---|
백준 1557 - 제곱 ㄴㄴ (1) | 2022.12.20 |
백준 23575 - Squid Game (1) | 2022.12.20 |