13137번 Exchange Problem

문제

백준 13137번 Exchange Problem

해결 과정

1. 문제 이해

이 문제는 DP와 그리디 알고리즘을 모두 사용하는 문제이다. 먼저 DP를 사용하여 동전의 최소 개수를 계산하고, 병찬이의 방법인 그리디 알고리즘을 사용하여 값이 일치하는지 확인하면 된다.

2. 동전 교환 DP 구현

먼저 DP를 사용하여 동전의 최소 개수를 계산해보자. 여느 동전 교환 문제와 같이, $dp[i]$를 $i$원을 만들기 위해 필요한 최소 동전의 개수라고 정의하자. 그러면 $dp[i]$는 다음과 같이 정의할 수 있다.

$$dp[i]=\underset{j=0}{\overset{n-1}{\min }}(dp[i-p[j]]+1)$$

이때 $dp[0]=0$이다. 이를 코드로 구현하면 다음과 같다.

vector<int> dp(2 * p[n - 1] + 1);
for (int i = 0; i <= 2 * p[n - 1]; ++i) dp[i] = i;
for (int i = 1; i <= 2 * p[n - 1]; ++i) {
  for (int j = 0; j < n; ++j) {
    if (p[j] <= i) dp[i] = min(dp[i], dp[i - p[j]] + 1);
  }
}

3. 병찬이의 방법 구현

다음으로 병찬이의 방법을 구현해보자. 병찬이의 방법은 매 순간마다, 더 필요한 돈 이하의 액면을 가진 동전 중 가장 액면이 높은 동전을 선택하는 그리디 알고리즘이다. 다음과 같이 구현할 수 있다.

int greedy(int i, int n, vector<int>& p) {
  int cnt = 0;
  for (int j = n - 1; j >= 0; --j) {
    cnt += i / p[j];
    i %= p[j];
  }
  return cnt;
}

4. 병찬이의 방법과 DP의 결과 비교

이제 $1$부터 $2\times p[n-1]$까지의 모든 금액에 대해 DP로 최소 동전을 계산하고, 이후 병찬이의 방법인 그리디 알고리즘을 사용하여 값이 일치하는지 확인하면 된다. 만약 일치하지 않는다면, 병찬이의 방법이 최적이 아니라는 뜻이다. 따라서 false를 반환하고, 일치한다면 true를 반환하면 된다.

for (int i = 1; i <= 2 * p[n - 1]; ++i) {
  if (greedy(i, n, p) != dp[i]) return false;
}
return true;

예시 답안

위의 과정을 종합하여 다음과 같이 구현할 수 있다.

C++ 코드

Baekjoon/13xxx/13137.cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int greedy(int i, int n, vector<int>& p) {
  int cnt = 0;
  for (int j = n - 1; j >= 0; --j) {
    cnt += i / p[j];
    i %= p[j];
  }
  return cnt;
}
 
bool solve(void) {
  int n; cin >> n;
  vector<int> p(n);
  for (int i = 0; i < n; ++i) cin >> p[i];
 
  vector<int> dp(2 * p[n - 1] + 1);
  for (int i = 0; i <= 2 * p[n - 1]; ++i) dp[i] = i;
  for (int i = 1; i <= 2 * p[n - 1]; ++i) {
    for (int j = 0; j < n; ++j) {
      if (p[j] <= i) dp[i] = min(dp[i], dp[i - p[j]] + 1);
    }
  }
 
  for (int i = 1; i <= 2 * p[n - 1]; ++i) {
    if (greedy(i, n, p) != dp[i]) return false;
  }
  return true;
}
 
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  cout << (solve() ? "Yes" : "No");
  return 0;
}

• 출처: Hiyabye/Baekjoon - 13137.cpp

효율성 분석

시간 복잡도	공간 복잡도
$\mathcal{O}(n\times \max (p))$	$\mathcal{O}(n+\max (p))$

문제 풀이 팁

문제에서 동전의 단위 액면 값은 순증가 수열이라고 했으므로 정렬할 필요가 없다.

DP 유형의 문제를 풀 때는, 문제의 조건을 각 상태에 대한 정보로 나누어 저장하는 것이 좋다. 이 문제에서는 $dp[i]$를 $i$원을 만들기 위해 필요한 최소 동전의 개수로 정의했다.

그리디 알고리즘은 매 순간마다 최적의 선택을 하는 알고리즘이다. 따라서 매 순간마다 최적의 선택을 하는 방법을 생각해보자.

추가 학습 자료

• 위키백과 - 동적 계획법
• 위키백과 - 탐욕 알고리즘