[Gold V] 동전 2 - 2294
성능 요약
메모리: 33684 KB, 시간: 860 ms
분류
다이나믹 프로그래밍
문제 설명
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
출력
첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.
풀이
아이디어
Top-Down 방식으로서, 입력된 동전을 하나씩 빼는 과정을 통해 모든 경우의 수를 순회하고, DP를 통해 중복되는 계산을 제거한 뒤, 순서가 달라 중복되어 나오는 계산을 배제한다.
순서가 달라 중복이 된다는 말은 아래 예시를 통해 알 수 있다.
3 3
1
2
3이 경우에 나올 수 있는 경우의 수는 총 3가지이다 그러나 Top-Down으로 코드를 설계했더니 다음과 같은 부분이 중복이 된다
{1, 2}인경우와 {2, 1}인 경우 모두를 센다. 이를 제거해줄 방법을 찾아야 한다.
그래서 만약 DP테이블에 값이 이미 있다면 0을 반환하도록 하는 코드를 만들었다.
n, m = map(int, input().split())
coin = [int(input()) for _ in range(n)]
dp = [-1 for _ in range(m+1)]
def find(k):
s = 0
if k == 0:
return 1
if k < 0 or dp[k] != -1:
return 0
for c in coin:
s += find(k - c)
dp[k] = s
return dp[k]
result = find(m)
print(result if result != 0 else -1)하지만 이 코드에는 고려하지 않은 요소가 있었다. 또다시 문제를 대충 읽은 탓이다.
최솟값을 구해라! 인데 그걸 고려하지 않은것이다.
따라서 Depth가 필요하고, 그 Depth가 가장 작으면서 0을 만들어주는것을 구해야 한다. 또한 설계 오류도 있었다. 동전의 종류를 구할 뿐이지 개수를 구하지 않은 탓이다.
MAX = 9876543210
n, m = map(int, input().split())
coin = [int(input()) for _ in range(n)]
dp = [MAX for _ in range(m + 1)]
def find(N, dep):
# print(N, dp)
if N == 0:
return dep
if N < 0:
return MAX
for c in coin:
if N-c < 0:
continue
s = find(N-c, dep+1)
dp[N] = min(s, dp[N])
# print()
return dp[N]
result = find(m, 0)
print(result if result != MAX else -1)
위 코드는 내가 DP를 적용하려고 노력했던 코드이다. DP가 적용된것처럼 보이지만 사실 아니다.ㅋㅋㅋㅋㅋ
아무리 노력해도 내가 이 함수에 DP를 적용할 수 없었던 이유는 find 함수가 참조적 투명성을 가지지 않기 때문이다. 쉬운 말로 파라미터가 같으면 같은 값을 리턴해야하는데 내 함수는 그렇지 못한다. 즉, 설계 오류이다.
함수가 반환하는 값을 다시 생각해 봐야 한다.
로 두고 다시 한번 생각해보았다.
기저 사례는 크게 달라진 것이 없으니 반복문 부분만 조금 수정하면 될 듯해 보였다.
코드
import sys
sys.setrecursionlimit(int(1e8))
input = sys.stdin.readline
MAX = 9876543210
n, m = map(int, input().split())
coin = [int(input()) for _ in range(n)]
dp = [0 for _ in range(m + 1)]
def find(N):
if N == 0:
return 0
if dp[N] != 0:
return dp[N]
comp = MAX
for c in coin:
if N-c < 0:
continue
s = find(N-c) + 1
comp = comp if comp < s else s
dp[N] = comp
return dp[N]
result = find(m)
print(result if result != MAX else -1)회고
이 코드를 만들면서 최적화 방법을 매우매우 많이 고민했는데 특히
comp = comp if comp < s else s이 코드는 원래 min 함수를 통해 만들어졌었다. 그러나 계속 30% 정도에서 틀렸습니다. 가 나와 sys 함수도 써보고 난리를 친 다음에 혹시나 싶어서 검색해봤더니 min 함수의 경우 의 시간복잡도를 갖는다는것을 알 수 있었다. 단순 비교만 한다면 만에 해결 할 수 있으니까 동아줄 붙잡는 심정으로 해봤는데 이게 통과가 되었다..
사실 조금 충격이었던게 min 함수라 해봐야 일건데 이 작은 차이로도 정답과 오답을 가를 수 있었다는것이 신선했다.
진짜많은 노력의 흔적이다..
