TIL 007 그리디 대표유형

📕 동전0

👉 접근방법

동전이 오름차순이기 때문에 큰 쪽부터 내려오면서, 사용할 수 있는 최대를 사용.
동전이 배수 관계인가를 확인해야함
예를 들면, 1,9,10 동전으로 18을 만들면 성립이 되지 않음.

👉 코드

K = 목표액수
cnt = 0
for i in range(N-1,-1,-1):
    t = K // A[i]
    cnt += t
    K -= t*A[i]
print(cnt)

📕 회의실 배정

👉 접근방법

지금 진행가능한 회의중에서 가장 빨리 끝나는 회의를 고른다.
끝나는 시간 순으로 sort 시킨다.
시간을 회의 끝나는 시간으로 바꾼 뒤, 그 전에 시작하는 회의는 스킵.

👉 코드

A.sort(key=lambda x: (x[1],x[0]))
ans = 0
t = 0
for i in range(N):
    if A[i][0] < t: continue
    ans+=1
    t = A[i][1]
print(ans)

📕 신입사원

👉 접근방법

성적이 모두 다른 사람보다 낮은 사람을 걸러낸다.
성적1에 대해 sort시킨 후, 1등인 사람의 성적2를 min 값으로 잡고 이보다 작은 사람을 걸러 나간다.
성적2가 높은사람이 나오면 min값을 update한다.

👉 코드

A.sort()
ans = 1
mini = A[0][1]
for i in range(1,N):
    if A[i][1] < mini:
        ans += 1
        mini = A[i][1]
print(ans)