[BaekJoon 11047][⚪4] 동전 0
❓ 문제
🎯 난이도
Silver ⚪4
🧠 풀이
1. 내 풀이 (그리디)
- 알고리즘
Greedy
- 설명
그리디 알고리즘을 사용한 풀이이다.
이 문제는 그리디 알고리즘에 적합한 문제인데, 그 이유는 다음과 같다.
- 주어지는 값들이
단조 증가하고, 오름차순으로정렬된다. 최대/최소값을 구하는 문제이다.- 매번 하나의 선택을 해야 하며, 선택을 되돌릴 필요가 없다.
이 조건임에도 불구하고 그리디 알고리즘이 아니기 위해서는 반례가 필요하다. 예를 들어, 더 작은 동전을 쓰는 경우가 더 적은 동전을 쓸 수 있는 경우에는 '그리디'의 조건이 성립하지 않게 된다. 하지만 이 문제의 경우에는 동전들의 값이 모두 배수로 주어지므로, 이러한 반례가 절대 생기지 않는다.
하나의 반복문만을 가지므로, 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{}, iK{};
cin >> iN >> iK;
vector<int> vecCoin(iN);
for(int& iCoin : vecCoin)
{
cin >> iCoin;
}
int iResult{};
// 큰 수의 동전부터 하나씩 판별
for(int i = iN - 1; i >= 0; --i)
{
// 잔액 0이면 바로 탈출
if(iK == 0)
{
break;
}
// 현재 선택된 동전이 잔액보다 작거나 같은 때만
if(vecCoin[i] <= iK)
{
iResult += iK / vecCoin[i]; // 결과값에 나누기 더함
iK %= vecCoin[i]; // 잔액 갱신
}
}
cout << iResult;
return 0;
}
2. 추가 풀이 (DP)
- 알고리즘
Dynamic Programming
- 설명
동적 계획법 알고리즘을 사용하는 방법이다.
모든 그리디 알고리즘은 DP로 치환이 가능하므로, 이 문제 또한 그러하다.
점화식은 다음과 같다.
\[dp[n] = min(dp[n], dp[n - coin[i]] + 1)\]
이 점화식을 사용해서 모든 종류의 동전에 대해 가능한 모든 금액의 최적 결과값을 배열에 저장하는 방식이다.
그러나 이 DP 사용 풀이는 사실 틀린 풀이이다. 로직은 맞지만, 이 문제의 조건이 (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)이기 때문에 최대 금액인 경우에는 문제의 메모리 제한인 256MB을 넘어서 400MB가 되기 때문이다. 이 풀이를 올린 것은 이렇게 풀 수도 있다는 것을 정리하기 위함이고, 항상 문제의 조건을 잘 보고 사용할 알고리즘을 선택하도록 하자.
이중 반복문을 가지고, 반복문 조건식의 최대값이 N, K이므로 전체적인 시간 복잡도는 O(N · K)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{}, iK{};
cin >> iN >> iK;
vector<int> vecCoin(iN);
for(int& iCoin : vecCoin)
{
cin >> iCoin;
}
constexpr int INF{ static_cast<int>(1e9) };
vector<int> vecDP(iK + 1, INF); // DP 배열 선언
vecDP[0] = 0;
// 모든 동전의 종류, 가능한 액수에 대한 최적값을 구하는 DP 반복문
for(int i = 0; i < iN; ++i)
{
for(int j = vecCoin[i]; j <= iK; ++j)
{
vecDP[j] = min(vecDP[j], vecDP[j - vecCoin[i]] + 1);
}
}
cout << vecDP[iK];
return 0;
}
💭 후기
이 문제는 모든 조건이 그리디 알고리즘을 보장하는 문제였기에 그리 어렵지 않았다. 근데 사실은 그리디를 사용하는 문제는 대부분 풀이를 생각하고 나면 그리디였던 경우가 많아서 아직은 분별하는데 익숙치 않긴 하다.
그보다 중요한 것은 모든 그리디가 DP로 치환 가능함에도 불구하고, 이 문제처럼 조건 때문에 불가능한 경우도 있다는 것이다. 또한 DP의 시간 복잡도나 메모리 할당을 보아도 훨씬 비효율적이기도 하므로, 항상 조건을 잘 보고 '알고리즘'과 '컨테이너' 선택에 신중을 기하도록 하자.
Comments