43236

날짜: 2022년 1월 31일 오후 5:51

코드

Algorithm/43236.py at main · Junroot/Algorithm

풀이

처음에 접근한 방법은 모든 경우의 수를 구하는 것이다. 하지만 이 방법은 바위가 최대 50000개이고, 제거할 바위의 수가 1개에서 바위의 수만큼이므로, ${50000}C{25000}$ 도 계산해야되기 때문에 이 방식은 불가능하다.

두 번째로 생각한 방법은 가장 짧은 거리를 우선적으로 지우면서 탐욕적으로 계산하는 방법이다. 하지만 이 방법에는 문제가 있다.

거리 합치기 선택 가장 짧은 거리를 선택해서 다른 거리와 합칠 때, 왼쪽과 오른쪽 중에 어디에 합쳐야 될 지 알 수 없다. 처음에 나는 더 짧은 거리와 무조건 합치면 된다고 생각했는데 문제가 있었다. (4, 4, 3, 5)라는 예를 보면 쉽게 이해할 수 있다. 내가 생각한 방식의 결과는 5가 나오지만 최적의 답은 8이다.
시간 복잡도 문제 돌의 개수가 m이라고 가정하면 O(nm)이 발생한다. 최악의 경우는 50000 * 50000번 이 과정을 해야되는데 이는 속도가 너무 느리다.

이분 탐색 문제라는 것을 알고 있었기 때문에 결국 문제 타입을 참고하여 풀었다. 최소값이 [0, distance] 사이에서 발생하기 때문에 이 사이에서 이분 탐색을 하면된다.

이 때, 현재값이 큰지 작은지 판별하는 과정에 또 어려움을 겪었다. 기본적으로 현재값을 만족하기 위해 지워야되는 돌의 개수를 이용하여 판별한다. 거리 0 지점부터 시작해서 순서대로 확인하면서, 현재값을 만족하지 못하는 거리가 있다면 최소값을 만족할 때까지 돌을 지우면된다. count 가 지운 돌의 개수, latest 가 거리를 만족하지 못하는 최초의 돌의 인덱스다. 이 방식은 O(m*log(distance))이다.

count = 0
latest = 0
for i in range(1, len(rocks)):
    if rocks[i] - rocks[latest] >= expected:
        latest = i
    else:
        count += 1

코드#

풀이#

코드

풀이