Awesome

동전 문제는 그리디 알고리즘이 되는 이유가

예를 들어 화폐가 500원, 100원 두 가지라면 500과 100의 최소공배수가 더 작은 수(100)이기 때문이라고 한다.

100x5=500으로 표현 가능하지만 이러할 경우 500으로 표현하는 것이 유리하기 때문에,

내림차순으로 정렬한 후에 그리디 알고리즘으로 해결 가능하다는 것 같다.

만약 화폐가 500원, 400원이라면 500은 400의 자연수 배수로 표현할 수 없기 때문에 그리디 알고리즘으로 풀 수 없다고 한다.

answer = 0

price = int(input())
change = 1000 - price
bank = [500, 100, 50, 10, 5, 1]

for coin in bank:
    if change >= coin:
        answer += change // coin
        change %= coin
        if change == 0:
            break

print(answer)

분명 문제가 그리디 카테고리에 있었지만 처음엔 완전탐색으로 풀었던 것 같다.

0부터 시작해 가능한 경우를 다 세보면서, 최대 회의 수를 max로 두고 마지막 max를 출력하는 방식으로 풀었다.

그렇게 하니 예시에 대한 답은 맞췄지만 채점 중 시간초과가 나왔다.

결국 구글링으로 힌트를 찾았다.

포인트는 회의가 끝나는 시간을 기준으로 정렬한 후에 그리디로 푸는 것.

회의가 끝나는 시간을 기준으로 삼으면, 앞으로 회의를 진행할 수 있는 남은 시간이 많이 남기 때문이라는 것이다.

만약 이 문제 유형이 그리디라는 것을 몰랐다면, 그리디로 풀어낼 수 있었을까?

생각하지 못했을 것 같다.

아직 처음이니까, 풀다보면 감이 오겠지.

answer = 0

n = int(input())
timeTable = []
for i in range(n):
    timeTable.append(tuple(map(int, input().split())))
timeTable.sort(key=lambda t: (t[1], t[0]))

last = 0
for t in timeTable:
    if t[0] >= last:
        answer += 1
        last = t[1]

print(answer)