BOJ 21758: 꿀 따기 [Python 3]

DP를 이용한 문제이다.

 

이 문제를 풀 때, 제일 중요한 점은 처음에 벌통, 벌 두 마리 중 두 가지는 양 끝에 둬야한다.

이를 '귀류법'을 통해서 증명했는데,

귀류법이란 간단하게 말해서 증명하고자 하는 것을 반대되는 것을 옳다고 가정하고, 이가 모순됨을 증명하여 기존의 증명이 옳다는 것을 증명하는 방법이다.

 

이 문제에서는, 벌통이나 벌 두마리가 제일 양 끝에 있는 예시가 최적이 해가 아니라고 했을 때, 이들이 가운데에 몰려있는 경우의 합이 양 끝에서 더한 합보다 작기에 모순되고, 그래서 이들이 양 끝에 있어야한다, 라는 결론이 나온다.

 

 

이 문제는 '스페셜 저지' 문제로, 구현해낸 n의 범위에 따라서 점수를 매긴다.

최대한 시간 적합하도록 문제를 구현해야 100점이라는 완벽한 점수를 매길 수 있다.

 

n=int(input())
data=list(map(int,input().split()))
answer=0
total=sum(data[1:n-1])
firstsum=total+data[n-1]
thirdsum=0
for i in range(1,n-1):
    firstsum-=data[i]
    thirdsum+=data[i-1]
    answer=max(answer,total-data[i]+data[-1]+firstsum)
    answer=max(answer,total+data[i])
    answer=max(answer,total-data[i]+thirdsum+data[0])
print(answer)

for 문 안에 있는 세가지의 answer을 보라.

첫 번재 answer는 벌1, 벌2, 벌집 (벌1과 벌집이 양쪽 끝, 벌 2는 한 칸씩 움직여봄)

두 번째 answer는 벌1, 벌집, 벌2 (벌들을 양쪽 끝, 벌집을 한 칸씩 움직여봄)

세 번째 answer는 벌집, 벌1, 벌2 (벌집과 벌2를 양쪽 끝, 벌1을 한 칸씩 움직여봄)

으로 정의했다.

 

이 값들을 돌아가면서 최대 합을 구하면 된다.

 

반복문도 3개를 반복문으로 해결하기 때문에, 시간 복잡도는  O(n)이다.

(해당 알고리즘을 이용하지 않았다면, 시간 복잡도가 O(n^3)였겠죠?)