본문 바로가기

취업과 기본기 튼튼/코딩 테스트 노트

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

문제

거스름돈 (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;
}