[Algorithm] D-5 그리디 문제 (5585번, 1541번, 1931번)

5585 거스름돈

# https://www.acmicpc.net/problem/5585
# 거스름돈
change = [500, 100, 50, 10, 5, 1]

n = int(input())
money = 1000 - n
result = 0
for i in change:
    if money >= i:
        result = result + money // i
        money = money % i

print(result)

1541 잃어버린 괄호

a=list(input().split('-'))
num=[]

for i in a:
    sum=0
    print(i)
    n=i.split('+')
    print(n)
    for j in n:
        sum+=int(j)
    num.append(sum)
print(num)
result=num[0]
for j in range (1,len(num)):
    result=result-num[j]

print(result)

과정

55-50+40 에서 가장 최소가 되도록 괄호를 치면 55-(50+40)이다. -> 우선 -를 기준으로 나눠준다음 - 뒤에 있는 숫자를 모두 합치면 된다.

1931 회의실 배정

# https://www.acmicpc.net/problem/1931
# 회의실 배정
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.sort(key=lambda x: (x[0]))
data.sort(key=lambda x: (x[1]))
last = 0
result = 0
for i, j in data:
    if i >= last:
        result += 1
        last = j

print(result)

과정

회의를 끝나는 시간을 기준으로만 정렬을 해주면 된다고 생각해 처음에는 data.sort(key=lambda x: (x[1]))
이것만 사용했다 근데 계속 틀렸대
그래서 조건을 보니깐 회의의 시작시간과 끝나는 시간이 같을 수도 있다.
이 경우를 생각하면 1,3 3,3을 x[1]로 정렬했을때
3,3 1,3이 될수있으므로 처음에 data.sort(key=lambda x: (x[0]))이걸 한번 해줘야한다....!