문제 링크
문제 요약
페티야는 n개의 상금이 걸린 대회에 참가합니다.
- 페티야가
k점을 얻으면 1번부터k번까지의 상금 중 하나를 받을 수 있습니다. - 하지만 페티야가 상금을 선택하기 전에, 주최자는 1번부터
k번 상금 목록 중 하나를 제거합니다. 그 후 페티야는 남은k-1개의 상금 중 아무거나 하나를 선택할 수 있습니다. - 각 상금의 가치
a_i가 주어졌을 때,k가 2부터n까지 변할 때마다 페티야가 얻을 수 있는 보장된 최대 상금 가치를 출력해야 합니다. - 여기서 페티야는 자신의 상금 가치를 최대화하려 하고, 주최자는 페티야가 받을 상금 가치를 최소화하려 합니다.
풀이
이 문제는 페티야와 주최자 사이의 게임으로 해석할 수 있습니다. 페티야는 최대 이득을, 주최자는 페티야의 최소 이득을 유도하려 하므로, 전형적인 최소극대화(minimax) 접근이 필요합니다.
특정 k점수를 얻었을 때를 생각해봅시다. 페티야는 1번부터 k번까지의 k개 상금 중에서 하나를 선택할 수 있습니다. 주최자는 이 k개의 상금 중 하나를 제거할 것이고, 페티야는 남은 k-1개 중에서 가장 가치가 높은 상금을 선택할 것입니다.
주최자는 페티야가 받을 상금의 가치를 최소화하고자 합니다. 페티야가 1번부터 k번까지의 상금 중에서 선택할 수 있을 때, 이 상금들 중 가장 가치가 높은 것을 max1, 두 번째로 가치가 높은 것을 max2라고 합시다.
- 주최자가
max1상금을 제거하는 경우: 페티야는 남은 상금들 중에서max2를 포함하여 가장 가치가 높은 것을 선택할 것입니다. 이 경우 페티야가 받을 수 있는 최대 가치는max2입니다. - 주최자가
max1이 아닌 다른 상금을 제거하는 경우:max1상금은 목록에 남아있으므로, 페티야는max1상금을 선택할 수 있습니다. 이 경우 페티야가 받을 수 있는 최대 가치는max1입니다.
주최자는 페티야의 이득을 최소화하려 하므로, max1과 max2 중 더 작은 값인 max2를 페티야가 받도록 유도할 것입니다.
즉, max1 상금을 제거하여 페티야가 max2를 가져가도록 만들 것입니다. 따라서, 페티야가 k점을 얻었을 때 보장받을 수 있는 최대 상금 가치는 1번부터 k번까지의 상금 중 두 번째로 큰 값이 됩니다.
이러한 로직은 모든 k (2부터 n까지)에 대해 동일하게 적용됩니다. 즉, 우리는 각 k에 대해 a_1, ..., a_k 중 두 번째로 큰 값을 찾아야 합니다.
이를 효율적으로 계산하기 위해, 입력으로 주어지는 상금 가치 리스트 l을 순회하면서 현재까지의 최대값(first_max)과 두 번째 최대값(second_max)을 갱신하는 방식으로 문제를 해결할 수 있습니다.
first_max: 현재까지 고려한 상금들 중 가장 큰 가치second_max: 현재까지 고려한 상금들 중 두 번째로 큰 가치
정답 코드
import sys
def solve():
n = int(sys.stdin.readline())
l = list(map(int,sys.stdin.readline().split()))
first_max = l[0]
second_max = 0 # 상금 가치가 1 이상이므로, 0으로 초기화해도 문제 없음
ans = []
# k가 2부터 n까지 변하므로, 인덱스는 1부터 n-1까지 순회
for i in range(1, n):
# 새로운 값이 현재의 첫 번째 최대값보다 크거나 같다면
if l[i] >= first_max:
second_max = first_max # 기존 첫 번째 최대값이 두 번째 최대값이 됨
first_max = l[i] # 새로운 값이 첫 번째 최대값이 됨
# 새로운 값이 첫 번째 최대값보다 작지만, 두 번째 최대값보다는 크다면
else:
second_max = max(second_max, l[i]) # 두 번째 최대값을 새로운 값과 비교하여 갱신
# 현재까지의 두 번째 최대값이 k번째 상금을 선택할 때 보장되는 값
ans.append(second_max)
print(*ans)
if __name__ == "__main__":
solve()