알고리즘 연습 Level 6 | 프로그래머스
미완
Q.
물건 값보다 많은 돈을 낼 경우 거스름돈을 돌려주게 됩니다. 거스름돈은 한 금액의 돈으로 줄 수도 있지만, 여러 금액의 동전을 섞어 거슬러 줄 수 있습니다.
거스름돈이 N원일 때, 1원, 2원, 5원 동전이 있다면 몇 가지 방법으로 돈을 거슬러 줄 수 있을까요? change 함수를 통해 경우의 수를 반환해주는 함수를 만들어 보세요. K에는 사용할 수 있는 동전의 종류가 들어 있습니다.
예를 들어, N = 5이고 K = [1, 2, 5]이면 1원, 2원, 5원 동전을 가지고 5원을 맞추는 경우의 수를 찾으면 됩니다.
- 1원 5개
- 1원 3개, 2원 1개
- 1원 1개, 2원 2개
- 5원 1개
이렇게 총 4가지 경우가 있으면, 4를 리턴해 주면 됩니다.
A.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include<iostream> #include<vector> using namespace std; int change(int total, vector<int> coin) { int answer = 0; // 1. 목표 금액까지 누적할 벡터(DP) // ex. 0 1 2 3 4 5 -> dp[코인 종류][경우의 수] int coinCount = coin.size(); vector<vector<int>> dp(coinCount, vector<int>(total+1, 0)); // 2. 첫 번째 금액으로만 만들 수 있는 경우의 수 for(int i = 0; i <= total; i++) { dp[0][i] = (i % coin[0] == 0) ? 1 : 0; } // 3. 2에서 최초 동전(1원 또는 그 이상)으로 경우의 수를 생성하였으므로 // 다음 동전부터 카운팅 for(int i = 1; i < coinCount; i++) { for(int j = 0; j <= total; j++) { // 이전 계산해둔 DP값에 누적하기 위함 dp[i][j] = dp[i-1][j]; int numOfCoin = 1, amount = coin[i] * numOfCoin; while (j - amount >= 0) { dp[i][j] += dp[i-1][j - amount]; numOfCoin++; amount = coin[i] * numOfCoin; } } } answer = dp[coinCount-1][total]; return answer; } int main() { int total = 10; vector<int > test{2,3,5,7,8}; // 아래는 테스트로 출력해 보기 위한 코드입니다. cout<< change(total, test); } |
작성은 완료했는데.. 어디에 문제가 있는건지 제출이 안된다..
제출해보면 내가 제출한 답이 아닌 solution에서 -1278631이란 값도 나오고..
차라리 시간초과이면 가지치기라도 해볼텐데..반례가 떠오르지 않음.
