캠프 문제인데, 참 멋있는 문제다. 일단 문제 설명과 풀이는 나중에 정리하기로 하고 모범답안을 보고 풀었는데 시간초과가 나서 이것 저것 찾아보고 생각 좀 해봤더니 나는 vector에서 erase연산을 사용하는데 이 것이 문제였다. 직접 테스트를 해봤는데 10만번 erase하는 데도 시간이 꽤 걸렸다...그래서 찾아보니 vector가 배열 기반 컨테이너라고 한다... 그래서 erase나 insert를 하게 되면 요소를 밀어내거나 당겨야 하고, 매우 오래 걸리는 것 같다.
->근데 확실치는 않다. 다시 생각해보니 수정전 코드도 erase를 이용했는데, 그 당시에는 시간 초과없이 50퍼센트까지 갔었다. 그런 것을 보면 시간 초과가 난 이유가 꼭 erase때문은 아닌 것 같기도 하고... 여튼 erase를 사용하지 않고 구현해 봐야겠다.
이 문제는 그리디 알고리즘이 핵심인 문제이다. 간략하게 풀이를 적자면, 오른손에 들어야 할 검들은 꼭 가지고 있어야 한다. 그리고 왼손에 들어야 할 검의 범위들에서 오른손에 들 검들로 커버할 수 있는 범위들은 제외하고 나머지 범위들에서 최소의 검의 개수를 구하면 되는데 이 부분이 핵심이다. 여기서 최소의 검을 구하는 방법은 회의실 배정 문제를 푸는 방식과 똑같다. 즉 겹치지 않는 범위의 최대 개수를 구하면 그것이 그 범위들을 커버할 수 있는 최소의 검의 개수가 된다.
처음에는 잘 이해가 안 갔지만 생각해보니 이해가 됐다. 간단히 설명하면, 겹치지 않는 각 범위들을 커버하기 위해서는 각 겹치지 않는 범위당 검이 꼭 한 개씩 필요하다. 그렇기 때문에 겹치지 않는 범위의 최대개수가 곧 모든 범위를 커버할 수 있는 검의 최소 개수가 되는 것이다. 겹치지 않는 각 범위들의 최대 개수를 각 범위당 검 하나로 커버하고 나면 나머지는 자연히 커버가 된다. 혹시 커버가 안되는 범위가 있다면 겹치지 않는 범위가 더 있다는 것인데 이 것은 겹치지 않는 각 범위들의 최대 개수를 구했다는 것에 모순이므로 말이 안된다.
그런데 문제가 있다. 일단 핵심 알고리즘은 그리디 알고리즘이긴 한데, 쌍검 용사가 검을 왼손, 오른손에 들어야 하므로 즉 동시에 2개를 들고 있어야 하므로 만약 별 생각 없이 구했다가는 입력이 1 1 1과 같이 들어오는 경우는 틀리게 될 것이다. 오른손의 검으로 왼손검을 커버가능해도 왼손검도 하나 들고 있어야 하므로 두 개가 필요하다.
이 부분을 해결하는 것이 정말 골치 아팠고 결국 해결 못하고 풀이를 봤다.
하지만 의외로 당연(?)한 방법이었다...
왼손검의 범위들을 오른손 검으로 커버할 수 있는지 검사하는데, 만약 어떤 오른손 검으로 커버가 가능한 경우 그 오른손 검이 그 왼손검 범위와 같은 짝이었던 오른손 검인지 아니면 다른 오른손 검인지 확인한다. 다른 오른손 검이라면 그 왼손검 범위는 커버가능한 것이지만 만약 같은 오른손 검이라면 커버할 수 없으므로 다음 크기의 오른손 검을 살펴본다. 만약 다음 크기의 오른손 검으로 커버가 가능하다면 괜찮지만 그게 안된다면 그 왼손검 범위는 커버할 수 없다는 것이된다...
여기서 조금 헷갈릴 수 있는데 꼭 기억해야할 것이 오른손 검, 왼손 검 모두 오름차순 정렬이 되어있다는 사실이다. 그리고 왼손검은 중복이 제거되어 있다. 그렇기 때문에 바로 다음 인덱스의 오른손 검만 살펴보면 되는 것이다.
그리고 풀이에서는 erase를 쓰지 않고 커버가 불가능한 왼손검 범위들을 따로 저장해서 모으는 식으로 했는데, 둘 다 비슷한 방법이긴 해도 풀이의 방법이 훨씬 나아보인다.
또한 오른손 검으로 커버할 수 없는 왼손검 범위들을 조사할 때, lower_bound를 쓰는게 코드가 훨씬 깔끔해지는 것 같다. 나는 그냥 인덱스를 늘려가면서 하나씩 비교해가는 식으로 했다.
댓글 없음:
댓글 쓰기