[프로그래머스] 거스름돈 (C++, Java)

카테고리

동적계획법 (dynamic programming)

나만의 카테고리

동적계획법, 기억해둘만한 문제

문제 링크

programmers.co.kr/learn/courses/30/lessons/12907

코딩테스트 연습 - 거스름돈

요점

• DFS와 헷갈릴 수 있지만 잘 기억해놓고 DP로 풀자
• 표를 그려서

참고 지식

• Arrays.sort() - Java

풀이 (C++)

#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int solution(int n, vector<int> money) {
    vector<int> answer(100001);
    sort(answer.begin(), answer.end());

    answer.at(0) = 1;

    for (int i = 0; i < money.size(); i++) {
        for (int j = money.at(i); j <= n; j++) {
            answer.at(j) += answer.at(j-money.at(i));
        }
    }

    return answer.at(n) % 1000000007;
}

풀이 (Java)

import java.util.Arrays;

class Solution {
    public int solution(int n, int[] money) {
        int[] answer = new int[100001]; 
        Arrays.sort(money);

        answer[0] = 1;

        for (int i : money) {
            for (int j = i; j <= n; j++) {
                answer[j] += answer[j - i];
            }
        }


        return answer[n] % 1000000007;
    }
}

처음에 자신있게 DFS로 짰더니 가볍게 실패하고 디버깅을 해보니 코드가 너무 복잡해지고 어려워져서 아예 엎었습니다.

그리고 다른분들의 코드를 찾아보니 DP로 푸는 문제더군요

이 문제는 그냥 기억해두고 비슷한 문제가 나오면 DP를 활용해야겠다는 생각을 떠올리는게 중요할것 같습니다

 

---

알고리즘 초보가 정리한 글입니다

더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!