오늘의 학습 키워드
GREEDY 욕심쟁이!
그리디란?
- 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.
- 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있다.
- 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.
오늘의 문제
백준 14916번
https://www.acmicpc.net/problem/14916
입출력
그리디 적용해보기
거스름돈을 최소 동전 개수로 줄 수 있는 그리디 접근 방법을 사용한 풀이.
- 초기 상태 설정:
- 거스름돈의 액수를 n으로 입력받는다.
- 사용할 동전 개수를 카운트할 변수 cnt를 0으로 초기화한다.
- i는 현재 단계의 동전 사용을 의미하는 변수로, 초기값은 0이다.
- 동전 개수 계산 반복:
- 반복문을 사용하여 현재 거스름돈(n)이 5로 나누어 떨어지는지 확인한다.
- 만약 n이 5로 나누어떨어지면, 가능한 최대 5원짜리 동전으로 거슬러 주고, 동전 개수를 cnt에 더한다. 그런 후 반복을 종료한다.
- n이 5로 나누어떨어지지 않는 경우, 2원을 거슬러 주기 위해 n에서 2를 빼고, 동전 개수(cnt)를 증가시킨다.
- 만약 n이 음수가 되면 더 이상 거슬러 줄 수 없으므로 반복을 종료한다.
- 결과 출력:
- 반복문이 종료된 후, 만약 거스름돈을 모두 거슬러 줄 수 없는 경우(n < 0), -1을 출력한다.
- 그렇지 않은 경우, 최소 동전 개수를 출력한다.
그리디 탐색 순서 예시 (입력 예제 1 적용)
- 첫 번째 단계:
현재 거스름돈 n은 13원이다. n이 5로 나누어떨어지지 않으므로 2원을 사용하여 거스름돈을 줄인다.
- 거스름돈: 11원, 동전 개수(cnt): 1.
- 두 번째 단계:
현재 거스름돈 n은 11원이다. 다시 2원을 사용하여 거스름돈을 줄인다.
- 거스름돈: 9원, 동전 개수(cnt): 2.
- 세 번째 단계:
현재 거스름돈 n은 9원이다. 다시 2원을 사용하여 거스름돈을 줄인다.
- 거스름돈: 7원, 동전 개수(cnt): 3.
- 네 번째 단계:
현재 거스름돈 n은 7원이다. 다시 2원을 사용하여 거스름돈을 줄인다.
- 거스름돈: 5원, 동전 개수(cnt): 4.
- 다섯 번째 단계:
현재 거스름돈 n은 5원이다. 5로 나누어떨어지므로 5원짜리 동전을 사용하여 거스름돈을 모두 줄인다.
- 거스름돈: 0원, 동전 개수(cnt): 5.
따라서 거스름돈 13원을 줄이기 위해 필요한 최소 동전 개수는 5개이다.
1. 입력값 받기
n = int(input()): 거스름돈의 액수를 입력받습니다.
2. 반복문을 통한 거스름돈 계산
-
cnt = 0: 사용할 동전의 개수를 저장하는 변수. 처음에는 0으로 초기화. -
while True:: 거스름돈을 거슬러 줄 때까지 무한 반복.-
조건 1:
if n % 5 == 0:
먼저 거스름돈 n이 5로 나누어떨어지는지 확인.
만약 n이 5로 나누어떨어지면, 가능한 최대 개수의 5원 동전을 사용할 수 있다는 의미.
cnt += n // 5: 5원짜리 동전을 사용할 수 있는 개수를 cnt에 추가.
break: 이후 반복문을 종료합니다. -
조건 2:
else:
만약 n이 5로 나누어떨어지지 않으면, 2원짜리 동전을 사용하여 거스름돈을 줄임.
n -= 2: 2원짜리 동전을 하나 사용하고, 거스름돈에서 2원을 뺌.
cnt += 1: 동전 개수를 하나 증가. -
조건 3:
if n < 0:
만약 거스름돈이 음수가 되면 더 이상 거슬러 줄 수 없다는 의미이므로 반복을 종료.
break로 반복문을 빠져나가기.
-
3. 결과 출력
if n < 0:: 반복문이 종료된 후 거스름돈이 음수(n < 0)라면, 주어진 동전으로 거슬러 줄 수 없으므로 -1을 출력.else: print(cnt): 거스름돈을 모두 거슬러 줄 수 있었다면, 최소 동전 개수(cnt)를 출력.
왜 그리디로 풀까?
이 문제에서 항상 큰 단위의 동전부터 사용해도 최적의 해를 구할 수 있기 때문에 그리디 알고리즘이 적합하다.
큰 단위 동전(5원)을 최대한 먼저 사용하면, 동전의 총 개수를 최소화할 수 있다.
따라서 이 문제는 매 순간 최선의 선택을 함으로써 최적의 해를 찾는 그리디 알고리즘으로 풀 수 있다.
전체 풀이
n = int(input())
cnt = 0
while True:
if n % 5 == 0:
cnt += n // 5
break
else:
n -= 2
cnt += 1
if n < 0:
break
if n < 0:
print(-1)
else:
print(cnt)오늘의 회고
🔥 그냥 원래 생각대로 풀면서? 답에 최대한 가깝게 빨리 구해지는 방법이 그리디인 것 같다..정확한 목표에 대한 빠른 문제 해결 방법?
