[백준] 25635 - 자유 이용권

리스트의 max값보다 작은 값들의 합이 max값보다 크면 max를 어떻게든 다 소비시킬 수 있어서 총 합이 답이될 수 있고 ( max값을 소비시키면 그 max값이 없어진 리스트에서의 max는 무조건 나머지의 합보다 작을 수 밖에 없음)

합이 max값보다 작으면 max를 모두 소비를 못시킴. 그래서 max값 제외한 수들의 * 2 후, 마지막 max값을 쓰는 +1을 해서 답 도출 가능

문제 링크

https://www.acmicpc.net/problem/25635

문제 요약

준원이는 놀이공원에서 연속으로 같은 놀이기구를 타지 않으면서 최대한 많이 탈 수 있는 횟수를 구하려고 합니다. 각 놀이기구에는 탈 수 있는 횟수 제한이 주어집니다. 준원이가 연속으로 같은 놀이기구를 타지 않고 최대 횟수를 달성할 때, 그 값은 얼마일까요?

푼 방법

리스트의 max값보다 작은 값들의 합이 max값보다 크면 max를 어떻게든 다 소비시킬 수 있어서 총 합이 답이될 수 있고 ( max값을 소비시키면 그 max값이 없어진 리스트에서의 max는 무조건 나머지의 합보다 작을 수 밖에 없음)

합이 max값보다 작으면 max를 모두 소비를 못시킴. 그래서 max값 제외한 수들의 * 2 후, 마지막 max값을 쓰는 +1을 해서 답 도출 가능

 

정답 코드

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
tickets = list(map(int, sys.stdin.readline().split()))

tickets.sort()

if n==1:
    print(1)
    exit()
if tickets[-1] <= sum(tickets[:-1]) + 1:
    print(sum(tickets))
else:
    print(2 * sum(tickets[:-1]) + 1)

배웠던 부분

첨에 maxheap, minheap 써서 최대값, 최소값 빼낸 후 각 힙에 차를 넣고 답에 min값 * 2를 더하는 식으로 했었는데, 테케는 통과하는데 논리가 이상한건지 틀림.