2294. 동전2

문제

백준 2294번 동전2

---

풀이

잘못 풀었던 것

처음에 또 생각없이 dfs로 풀다가 시간초과 뜨고 정신차렸다.

def dfs(L, val, cnt):
    global res
    if cnt > res or val > k or L == len(coins): return
    if val == k:
        if cnt < res: res = cnt
    else:
        for i in range(len(coins)):
            dfs(i, val+coins[i], cnt+1)

if __name__ == '__main__':
    n, k = map(int, input().split())
    coins = [int(input()) for _ in range (n)]
    res = 1e9
    dfs(0, 0, 0)
    if res != 1e9: print(res)
    else: print(-1)
   

동적 프로그래밍으로 푸는데 아무리 봐도 맞는 코드인 것 같은데 계속 틀렸습니다 뜬다.
*(맞았는데 왜 자꾸 틀리대 ㅡㅡ) -> 맞기는 무슨...
문제해결하는대로 달려와서 글 수정하겠다..*

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]

dy = [0] * (k+1)
for c in coins:
    for i in range(c, k+1):
        if dy[i] == 0 and dy[i-c] == 0: 
            dy[i] = i//c if i%c == 0 else 0
        elif dy[i] == 0: 
            dy[i] = dy[i-c]+1
        elif dy[i] !=0 and dy[i-c] != 0: 
            dy[i] = min(dy[i], dy[i-c]+1)
print(dy[k]) if dy[k] != 0 else print(-1)

조건분기를 전혀 잘못 설정했었다.
1) dp[i]와 dp[i-c] 둘 다 0일때
2) dp[i]만 0일 때
3) dp[i-c]만 0일 때
4) 둘 다 0이 아닐 때

이렇게 설정했는 데도 자꾸 틀렸습니다 떴다.

그리고나서 깨달은 것은,

• 만들어야하는 금액보다 동전의 금액이 더 클 때 -> break

왜 브레이크 했냐면 나는 동전이 오름차순으로 들어오는 줄 알았다.
이 때 또 틀렸습니다 떠서 진짜 관두기 일보직전이었음.

"아 뭐가 문젠데🤬" x 100번 외치고 정신부여잡고 coin.sort() 집어넣었다.

아 드디어 해결..🤮

n, k = map(int, sys.stdin.readline().split())
coin = list(int(sys.stdin.readline()) for _ in range(n))
coin.sort()

dp = [0] * (k+1)
for c in coin:
    if c > k: break;
    dp[c] = 1
    for i in range(c+1, k+1):
        if dp[i] == 0 and dp[i-c] == 0: continue
        elif dp[i] == 0: dp[i] = dp[i-c] + 1
        elif dp[i-c] == 0: continue
        else: dp[i] = min(dp[i], dp[i-c]+1)
print(dp[k]) if dp[k] else print(-1)