그리디 알고리즘, 원인과 결과 찾기

🧑‍💻 그리디 알고리즘, 원인과 결과 찾기

멀티잇 코딩테스트 러닝클래스'Python 5월반

 

 

거스름돈

1, 5, 10, 20, 40 원이라는 동전이 있다

N원을 거슬러 주기 위한 최소의 동전의 개수를 구하는 것

기본적으로 40부터 시작해서, 남은 나머지를 계산해주면 된다

 

N = int(input())
coin = [40, 20, 10, 5, 1]
count = 0

for c in coin:
    if c <= N:
        count += N // c
        N = N % c

print(count)

---

 

 

 

구름 스퀘어

행사 시작 시간과 끝나는 시간이 주어진다

• 행사가 끝나고 최소 1시간을 쉬고, 다음 행사를 진행할 수 있다

행사들이 겹치지 않으면서 최대 개수를 출력한다

생각해볼 수 있는 경우의 수들

• 빨리 시작하는 기준으로 정렬
• 제일 빨리 끝나는 기준으로 정렬
• 시간이 제일 짧은 기준으로 정렬

 

여기서는 제일 빨리 끝나는 기준으로 정렬을 한다

N = int(input())

time = []
for _ in range(N):
    time.append(list(map(int, input().split())))

time.sort(key=lambda x: (x[1], x[0]))

count = 0
temp_end = 0
for start, end in time:
    if start > temp_end:
        count += 1
        temp_end = end

print(count)