[Greedy] 백준 풀긔

1번) https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

n = int(input())

meetings = []
for _ in range(n):
    meetings.append(list(map(int, input().split())))
    
meetings.sort(key = lambda x: (x[1], x[0]))

count = 0
end_time = 0

for index in range(n):
       
    if end_time <= meetings[index][0]:
        end_time = meetings[index][1]
        count += 1
    
print(count)

 

"가장" 빨리 끝나는 회의 순으로 정렬 후, 가능한 회의를 count

→ 회의가 끝나는게 빠를 수록 더 많은 회의를 감당할 수 있음

 

 

2번) https://www.acmicpc.net/problem/11399

11399번: ATM

n = int(input())
p = list(map(int, input().split()))
p.sort()

result = 0
for i in range(n):
    result += p[i]*(n-i)
    
print(result)

 

"가장" 적은 시간이 걸린 사람이 "가장" 먼저 업무 보기

→  맨 뒷 순서는 1번만 더하면 되고, 맨 앞 순서는 인원수 만큼 더하면 되기 때문에, 걍 정렬하면 됨.

 

3번) https://www.acmicpc.net/problem/1541

 

s = input()
str = s.split("-")

add = 0
if str[0] != "":
    add += sum(list(map(int, str[0].split("+"))))

str.pop(0)

sub = 0
for x in str:
    sub += sum(map(int, x.split("+")))

print(add-sub)

-가 나오면 그 뒤는 -까지 더하면 댐

 

4번) https://www.acmicpc.net/problem/13305

import sys

n = int(sys.stdin.readline())
road_lengths = list(map(int, sys.stdin.readline().split()))
gas_price = list(map(int, sys.stdin.readline().split()))

total_price = 0
min_price = sys.maxsize

for _ in range(n-1):
    total_price += road_lengths[0] * min(gas_price[0], min_price)
    min_price = min(gas_price[0], min_price)
    
    road_lengths.pop(0)
    gas_price.pop(0)

print(total_price)

"가장" 작은 처음 시작부터 갱신해가면 최소 기름값으로 갈 수 있음.