그리디 알고리즘
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법이며 탐욕법이라고도 한다.
- 가장 좋아 보이는 것을 선택하는 것이기 때문에 항상 최적의 해결책을 제공하지는 않는다.
- 그렇기에 코테에서는 탐욕법으로 얻은 해가 최적의 해가 되는 상황을 주고 이를 추론할 수 있어야 풀리도록 출제가 된다고 한다!
코드
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
coin = []
cnt = 0
for _ in range(N):
coin.append(int(input()))
for i in range(N-1, -1, -1):
if K >= coin[i]:
cnt += K // coin[i]
K %= coin[i]
print(cnt)
- 사실 탐욕법을 모르더라도 풀 수 있는 문제였다.
- 이렇게 푸는 게 탐욕법이구나 알게 해준 문제다.
- 코드를 짜면서 가장 큰 수로 나누는 방법으로 동전이 딱 나누어떨어지지 않으면 어떡하지? 그러면 그 다음 큰 수로 나누어 보아야 되는데? 라는 생각이 들었다.
그러나 이 문제는 탐욕법을 이용한 코테 문제! 그래서 딱 나누어 떨어지는 수만 주는 것 같다.
- 한 가지 실수를 한 것이 있는데, 처음에 2번째 for문에서 K>coin[i]로 작성해버려서 틀렸습니다가 나왔다..!
당연히 K가 딱 떨어질 수도 있는데 뇌를 빼고 썼나... 하나하나 조심해서 작성하도록 하자.
for문 대신 in 사용
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
coin = []
cnt = 0
for _ in range(N):
coin.append(int(input()))
coin.reverse()
for i in coin:
if K >= i:
cnt += K // i
K %= i
print(cnt)
- 2번째 for문을 coin 리스트를 이용해서 in을 사용해서 작성해본 코드이다.
- coin의 가장 뒤부터 돌아야 하기에 reverse로 반대로 정렬해주었다.
결과
- 오호 별로 차이가 안 날 거라 생각했는데 꽤 난다. 위에가 in 사용한 코드!
