[BOJ][Python3/PyPy3] 15553 - 난로

아무리 고민해봐도 해답을 알 수 없었던 문제였던 난로 문제에 대해 정리해보고자 한다.

(결국 다른 사람의 아이디어를 참고하여 내 나름대로의 방법으로 풀었다)

당연히 처음에 떠올렸던 풀이는 시간 간격별로 잘라서 비교하는 것이었는데,

처음에는 그 방법으로 풀 수 없다고 생각했다.

 

단순히 인접한 친구의 방문 시간 간격이 길 수록 성냥을 먼저 쓴다고 생각하기에는

그렇게 소비한 성냥 때문에 오히려 더 많은 시간에 난로를 지펴야 하는 것 아닌가 하는 생각을 했다.

 

 

사실 문제를 풀면서 계속 헷갈렸던 것이, 친구가 올 때까지 난로를 핀다는 이상한 생각에 계속 사로잡혀 있었다.

가령 다음과 같이 친구가 방문을 하는 상황에 성냥이 2개 있다고 하자.

최적해의 알고리즘대로라면 '10' 시간에 방문하는 친구가 올 때 난로를 펴야 한다.

 

여기에서 자연스럽게 이상한 기분이 들었다.

그럼 그 전에 1부터 6까지는 난로를 펴야한다는 말인데, 이건 손해 아닌가?

어쩌면 저 동그라미 개수를 난로를 피는 시간과 헷갈린 것같기도 하다.

왼쪽에 3개, 오른쪽에 1개

3개 시간동안 난로를 피우고 끊었다가 오른쪽에 하나를 난로를 피운다?

뭔가 손해같았다.

 

그래서 1과 10의 중간인 5와 가장 가까운 숫자부터 난로를 피우고,

난로를 피운 두 시점 사이의 중간점과 가까운 곳에서 난로를 피우고,,

이런 매우 복잡한 풀이를 고민하기에 이르렀다.

이게 맞는 풀이인지 확인도 안됐을 뿐더러, 그게 맞는 풀이라고 하더라도

이걸 구현할 자신이 도저히 없었다.

그래서 결국 1시간 동안 고민한 끝에 검색을 했다..

 

다른 사람의 풀이와 설명을 봐도 이해가 갈듯 말듯 헷갈렸다.

결국 내가 이해한 방법은 다음과 같다.

 

1부터 10까지 총 10개의 시간이 있다.

그것을 맨 처음 친구가 방문하는 시간 1과 나머지 시간 간격의 합으로 생각하자.

위 예시에서는 1 + (2 + 3+ 4) = 10 이 된다.

앞에 1을 따로 빼는 이유는 첫 친구가 왔을 때는 '간격'이 없고,

처음에는 무조건 난로를 피워야 하므로 난로를 피우는 시간이 아무리 적어도 무조건 1은 존재하기 때문이다. 

 

이제 우리가 해결해야 하는 것은 이 시간 간격의 합을 최소로 만드는 것이다.

주어진 총 10개의 시간 중 난로를 피우는 시간을 최소로 줄이기 위해서는 나머지 시간 간격의 합을 줄어야 한다.

시간 간격의 합을 줄이는 방법은 난로를 피우는 것이다.

 

예를 들어 10 시점에 난로를 피운다고 하자.

그렇다면 '10'에 친구가 올 때 난로를 피울 것이기 때문에,

이 전에는 굳이 난로를 틀고 있을 필요가 없다.

따라서 (7, 8, 9, 10) 4개의 시간을 10에 한번만 난로를 피워서

1개의 시간으로 줄여버릴 수 있다.

 

이걸 떠올리는게 조금 힘든 문제였다. 그래서 solved.ac 티어가 골드 4인 것 같다.

또 이 문제가 개인적으로 어려웠던 이유는,

보통 다른 문제는 특정 시점을 선택하면, 그 선택이 이후의 과정에 영향을 주는 것을 고려해야 한다.

그러나 이 문제는 특정 시점에 난로를 틀기로 선택하면, 그 선택으로인해

그 "전"시간의 난로를 틀어두는 시간이 줄어든다.

하나의 선택이 그 이전의 과정에 영향을 주는 것이다.

개인적으로는 그래서 더 헷갈렸다..

 

10의 시간에 난로를 틀면 더이상 이후에 친구가 방문하지 않으니

난로를 트는 이유가 없지 않나 이전부터 틀어두는게 이득이지

이런 생각을 자연스럽게 하고 있었다ㅋㅋ

(현실적인 난방비 걱정을 한건가..)

 

이제 아이디어를 떠올린 이후 구현은 매우 간단하다.

매 시간 간격을 전부 배열에 저장한다.

그 다음 배열을 오름차순으로 정렬하고 하나씩 pop을 했다.

(파이썬의 pop은 맨 뒤의 원소를 뺄 때 한정으로 O(1)의 시간복잡도를 가진다.)

 

만약 성냥이 남아있다면 pop한 값을 무시하고, 난방시간에 1을 더한다.

성냥이 남아있지 않다면 난방시간에 pop한 시간을 더해준다.

 

다른 사람들의 풀이 중에는 우선순위 큐를 활용한 풀이가 많이 보였다.

나는 우선순위 큐를 활용하지 않고 풀어보았다.

 

# 15553 난로
import sys
friends, match = map(int,input().split())
interval = []
start = -1
match -= 1 # 맨 처음에는 반드시 성냥을 써야하므로 하나 빼준다.
for _ in range(friends):
    arrive = int(sys.stdin.readline())
    if start == -1: #시작 값이 정해지지 않은 경우(맨 처음)
        start = arrive
        continue

    interval.append(arrive - start)
    start = arrive

interval.sort()
answer = 1
for i in range(len(interval)):
    if match:
        answer += 1
        interval.pop()
        match -= 1
    else:
        answer += interval.pop()

print(answer)