[프로그래머스] 거스름돈

문제

거스름돈 (https://programmers.co.kr/learn/courses/30/lessons/12907)

풀이

1. 초기접근

• 문제 조건 해석

  • n은 100,000 이하의 자연수입니다. 화폐 단위는 100종류 이하입니다. -> O(nm) 안에 풀어야함.

  • 문제 조건의 변수로, 다음이 주어짐.

    • 거슬러 줘야 하는 금액 n

    • 돈의 종류 money

  • 거슬러줘야하는 금액 n과 돈의 종류에 따른 경우의 수를 고려해야 하므로, 두 가지를 고려한 2차원 dp를 생각할 수 있음.

• 2차원 dp

  • d[j][i] = (money[0] 부터 money[j] 의 화폐를 가지고 i원을 낼 수 있는 방법의 수) 라고 하면, 목표하는 정답은 d[money.size()-1][n] 가 됨.

  • 먼저 어떤 화폐를 쓰던, 0원을 거슬러주는 방법의 수는 1이므로, 모든 j에 대하여, d[j][0] = 1 임.

  • d[j+1][i] 는 먼저, money[j] 를 가지고 만든 i원을 만드는 방법을 그대로 할 수 있으므로, d[j+1][i] = d[j][i] 임.

  • 여기에, money[j+1] 을 가지고, i원을 만드는 방법이 추가되므로, i원에서 money[j] 를 한 번 빼주면, i-money[j] 원을 만드는 방법과 동일.

• 코드

#include <string>
#include <vector>
​
using namespace std;
​
long long d[101][100001];
​
int solution(int n, vector<int> money) {
  int answer = 0;
​
  d[0][0] = 1;
  for (int i=money[0] ; i<=n ; i+=money[0])
    d[0][i] = 1;
​
  for (int j=1 ; j<money.size() ; j++)
    for (int i=0 ; i<=n ; i++)
      if (i >= money[j])
        d[j][i] += d[j][i-money[j]] % 1000000007;
​
  answer = d[money.size()-1][n];
  return answer;
}

2. 메모리 효율올리기

• 위와 같이만 하면, 효율성 테스트에서 모두 시간초과가 뜨는데, 다음과 같이 바꿔주면 된다.

• 위 2차원 배열을 보면 d[j+1][i] 가 d[j][i] 를 그대로 가져오는걸 볼 수 있는데, 사실상 1차원 배열만 쓰면 된다.

• 코드

#include <string>
#include <vector>
​
using namespace std;
​
long long d[111111];
​
int solution(int n, vector<int> money) {
  int answer = 0;
​
  d[0] = 1;
  for (int i=money[0] ; i<=n ; i+=money[0])
    d[i] = 1;
​
  for (int j=1 ; j<money.size() ; j++)
    for (int i=0 ; i<=n ; i++)
      if (i >= money[j])
        d[i] += d[i-money[j]] % 1000000007;
​
  answer = d[n];
  return answer;
}