[백준 11047 파이썬] 동전 0 (실버2, 그리디)

알고리즘 유형 : 그리디(greedy)
풀이 참고 없이 스스로 풀었나요? : O

https://www.acmicpc.net/problem/11047

SOLVE 1

그리디 풀이

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]
count = 0

for coin in coins[::-1]:
    pos = K // coin
    if pos:
        K -= coin * pos
        count += pos
    if K == 0:
        print(count)
        break

SOLVE 2

DP 풀이(메모리 초과)

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
coins = list(reversed([int(input()) for _ in range(N)]))

DP = [0]*(K+1)
DP[1] = 1

for cost in range(2, K+1):
    for coin in coins:
        if cost // coin > 0: # 이거 주석 아니고 몫 연산자임!!
            DP[cost] = DP[cost % coin] + cost // coin # 이거 주석 아니고 몫 연산자임!!
            break

print(DP[K])

SOLVE 1) 풀이 요약 (그리디 풀이)

1. 오름차순으로 주는 동전을 그대로 리스트에 담기

2. DP로 풀 수도 있지만, 그리디로 최적해를 구할 수 있는 문제이기도 하고 애초에 K가 1억까지 주어지기에 DP로 풀면 메모리 초과남(1원부터 K원까지의 최소 동전 수를 다 구하기 때문)

3. 그리디로 풀면, 가장 큰 동전을 고른다. 최대로 가능한 만큼 K에서 차감한다. 그 다음으로 큰 동전을 고르고 또 가능한 만큼을 K에서 싹 다 빼준다. 예를 들어, 4200의 경우 1000원 4개 빼고 200원 남고, 100원 2개 빼면 총 6개로 4200원 다 빼게 됨.

4. 이렇게 각 단계마다, 그 단계에서 최선이라고 생각되는 경우를 실행하고, 그 것이 마지막까지 쭉 이어져서 얻은 결과가 general optimal solution이 된다면 그 문제는 그리디 알고리즘으로 풀 수 있는 문제인 것이다. 모든 경우를 조사하는 DP와 달리, 그리디는 되는 문제도 있고 안 되는 문제도 있다.

SOLVE 1) 배운 점, 부족했던 점

• 그리디 알고리즘이 무엇인지, 어따 써먹는건지, DP와의 차이점은 무엇인지, 장단점은 무엇인지 알았다. 뭘 알았는지는 저기 위 풀이 요약 4번에 적어놨고, 추가로 장단점을 적어보자면, 우선 DP는 모든 경우를 조사하여 최적해의 일반해로서의 신뢰도가 높지만 시공간복잡도가 높고, 그리디는 시공간복잡도가 낮지만 구한 최적해가 일반해일 수도 있고, 일반해에 가까운 근사값일 수도 있다.

SOLVE 2 풀이 요약 (DP 풀이, 메모리 초과)

1. K+1 길이의 리스트 "DP"를 할당한다. 인덱스가 곧 액수를 의미한다.

2. N원을 채우는 최소 동전 개수 DP[N]은, 동전들을 내림차순으로 담은 coins 리스트를 돌면서, 가장 큰 동전부터 돌면서 N을 동전으로 나눴을 때 한 번 이상 나눠지는 것 중 처음 만나는 것(가장 큰 동전)에 대해, 그 동전으로 뺄 수 있는만큼 N에서 빼고, "그 나머지 T에 대해 DP[T]와 동전으로 N에서 뺀 횟수만큼을 더해준 값"이다.