🧑💻 그리디 알고리즘, 원인과 결과 찾기
멀티잇 코딩테스트 러닝클래스'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)
'알고리즘 > 알고리즘 설명' 카테고리의 다른 글
그래프 탐색 (0) | 2023.05.25 |
---|---|
다이나믹 프로그래밍 (0) | 2023.05.24 |
기초 자료구조의 구현과 응용 (0) | 2023.05.22 |
완전 탐색 (0) | 2023.05.11 |
시뮬레이션과 창의적 해결 (2) | 2023.05.09 |