BOJ-13305 S3🥈 주유소

풀이 소요시간 : 15분 ⏰

n = int(input())
dist = [0] + list(map(int, input().split()))
cost = list(map(int, input().split()))

current_cost = 987654321
result = 0

for i in range(n-1):
    if cost[i] < current_cost:
        current_cost = cost[i]
    result += (current_cost * dist[i+1])

print(result)

회고

• 아이디어를 떠올리는게 어렵지 않았다.
• 풀고나서 알아보니 "스탈린 정렬🛠️" 이라는 이름이 있었다..ㅋㅋ
• 현재 지점의 주유소 가격이 다음 주유소 가격보다 비싸다면 다음 주유소에서 쳐낸다.

---

BOJ-17503 S1🥈 맥주 축제

• 풀이 못함

import sys
import heapq

n, m, k = map(int, sys.stdin.readline().split())

# 선호도 순서로 정렬하여 입력
beers = [list(map(int, input().split())) for _ in range(k)]
beers = sorted(beers,key=lambda x: (x[1],x[0]))
preference = 0
pq = []

for i in beers:
    preference += i[0]
    heapq.heappush(pq, i[0])

    if len(pq) == n:
        if preference >= m:
            answer = i[1]
            break
        else:
            preference -= heapq.heappop(pq)
else:
    print(-1)
    exit()

print(answer)

회고

• 풀이 못해서 블로그 글 보고 이해함
• 맨 처음 아이디어는 위 코드처럼 정렬하고 탐색을 bisect_left로 하는 방식으로서 시간복잡도를 줄이려고 했으나, 구현에 실패하였다.
• 사실 한두번 찾는게 아니라 힙을 사용하는 아이디어는 좋은 것 같다.
• 풀면서 생각한건데 다이나믹이랑 그리디랑 구분하는게 쉽지 않겠다라는 생각이 들었다.
  - 위 코드는 heap에서 빼는 경우가 있지만 구현하려 했던 이분탐색 코드에서는 선호도를 초과했을 경우에 건너뛰는 경우를 구현하기가 난해했다.
  

---

BOJ-2212 G5🥇센서

n = int(input())
m = int(input())
lst = list(map(int, input().split()))
lst.sort()
dist = [lst[i] - lst[i-1] for i in range(1, n)]

print(sum(sorted(dist)[:len(lst) - m]))

회고

• 그리디라는걸 알고 풀지 않았다면 무조건 시간초과로 틀렸을 문제
• 아이디어는 센서간의 거리를 오름차순 정렬 한 뒤 각각의 거리를 구하여 dist에 저장하였다.
• dist에 있는 값을 정렬 한 뒤, 긴 거리부터 그리디하게 빼주는 방법을 이용한다.

---