hanadamoh   3년 전

평범한 배낭, 평범한 배낭2 코드 참고해서 풀었어요

우선 평범한 배낭2에서 같은 동전이 여러개 주어졌을 때 코드를 줄이기위해 이용한 방법 그대로 이용해서,

동전 1원이 7개 있다면

(4원,1) (2원,1) (1원,1) 을 다른 동전으로 묶어 만들어서.

위에 동전 다쓰면 7원이 되는 셈이고 두 개만 쓰면 6원 또는 3원 또는 5원이 만들어지고 하나만 쓰면 4원 2원 1원

또 동전 1원이 4개 있다면

(2원, 1) (1원, 1) (1원, 1) 을 각가 다른 동전으로 묶어 만들어서.. 이런 방식으로요.

그리고 평범한 배낭 푸는 방식으로

위에서 정리한 동전 묶음을 0~i번째 동전으로 각각 생각해서

dp[i][j][0]: 0~i번째 동전까지 내서 j원을 맞출 때 낼 수 있는 최대 동전 개수dp[i][j][1]: 사용한 동전별 개수 [penny, dime, nickle, quarter]

으로 이중 포문 돌렸어요

그런데 틀렸다고 나와요.ㅠㅠ 하루종일 짠 코드인데 해결을 못했어요 


도움 부탁드려요.ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.