https://www.acmicpc.net/problem/20115 코드n = int(input())drinks = list(map(int, input().split()))drinks.sort()ans = drinks[-1]for i in range(len(drinks)-1): ans += (drinks[i]/2)print(ans) 처음에는 남은 음료들 중 가장 양이 적은 2개를 골라서 합쳐야 하는줄 알았는데, 아니었다. 매 순서에 2로 나누어지는 음료들을 최대한 작게 해주어야 하는데, 이렇게 하면 그럴 수 없다.예를 들어, 음료 5개가 가장 작은 것부터 순서대로 a, b, c, d, e 이렇게 있다고 하면 원래 생각한 방법대로면 처음에 a, b를 뽑아서 (a/2)+b를 만들게 된다. 그 다음 순서..
문제풀이/Greedy
https://www.acmicpc.net/problem/17451 코드import sysinput = sys.stdin.readlinen = int(input())v = list(map(int, input().split()))ans = v[-1]for i in range(n-2, -1, -1): if ans % v[i] != 0: ans = (ans//v[i]+1)*v[i]print(ans) 처음에 Parametric Search로 풀이했다가 시간 초과가 발생하였는데, Parametric Search 알고리즘만 하면 시간 복잡도가 O(logN)인데 조건 검사할 때마다 O(N)이 추가로 필요해서 그런 것 같다. 그래서 다시 살펴보니 Greedy로 풀이할 수 있을 것 같아서 바꾸었다. 행..
https://www.acmicpc.net/problem/19598 코드from heapq import heappop, heappushn = int(input())time = []for _ in range(n): s, e = map(int, input().split()) time.append((s, e))time.sort() # 시작 시간을 기준으로 오름차순 정렬hq = [] # 우선순위 큐 => 사용 중인 회의실들의 사용 종료 시각for i in range(n): if hq and hq[0] 1개의 회의실이 아닌 최소의 회의실을 사용하여 N개의 회의를 모두 진행해야 한다. 그렇기 때문에 매회의마다 지금 당장 사용 가능한 회의실이 있다면 거기로 넣고, 없다면 새로운 회의실을 하나 추..
11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 코드 for _ in range(int(input())): n = int(input()) lst = list(map(int, input().split())) highest = -1 ans = 0 for i in range(n-1, -1, -1): if highest < lst[i]: highest = lst[i] else: ans += (highest-lst[i]) print(ans) 풀이는 간단하다. 날짜를 역순으로 가며 최대 주식 가격인 highe..
4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 코드 idx = 1 while True: l, p, v = map(int, input().split()) if l == 0 and p == 0 and v == 0: break ans = v//p*l + (v % p if l >= (v % p) else l) print(f"Case {idx}: {ans}") idx += 1 다른건 쉽지만 V%P의 값이 L보다 큰 경우를 조심해야 한다. 이 경우는 주어진 휴가일수보다 V%P가 커지는 경우이기 때문이다.
