C++ 코딩테스트 강좌, 동전 개수의 최솟값 구하기

안녕하세요! 오늘은 C++ 코딩 테스트에서 자주 출제되는 문제 중 하나인 ‘동전 개수의 최솟값 구하기’에 대해 알아보겠습니다. 이 문제는 기본적인 알고리즘 문제로, 주어진 금액을 만들기 위해 필요한 최소한의 동전 개수를 구하는 문제입니다. 저희는 이 문제를 단계별로 분석하고, 구현 과정을 통해 해결해보겠습니다.

문제 설명

주어진 동전의 종류와 목표 금액이 있을 때, 해당 금액을 만드는 데 필요한 최소의 동전 숫자를 구해보세요. 각 동전은 무한히 사용 가능하다고 가정하겠습니다.

입력 형식

  • 첫 번째 줄에 동전의 종류 N (1 ≤ N ≤ 100) 이 주어집니다.
  • 두 번째 줄에 각 동전의 가치를 나타내는 N개의 정수들이 주어집니다.
  • 세 번째 줄에 목표 금액 M (1 ≤ M ≤ 10,000)이 주어집니다.

출력 형식

  • 목표 금액을 만들기 위해 필요한 최소의 동전 개수를 출력합니다. 만약 목표 금액을 만들 수 없는 경우 -1을 출력합니다.

예제

예제 입력:
3
1 3 4
6

예제 출력:
2

위의 예제에서는 동전의 종류가 3개이고, 각 동전의 가치는 1, 3, 4입니다. 목표 금액 6을 만들기 위해서 동전 3과 3을 사용하면 총 2개의 동전으로 만들 수 있습니다.

문제 해결을 위한 접근 방법

이 문제는 동적 프로그래밍(Dynamic Programming) 또는 그리디 알고리즘(Greedy Algorithm)으로 해결할 수 있는 문제입니다. 하지만 동전의 종류가 여러 개일 경우, 동적 프로그래밍을 사용하여 보다 일반적인 해법을 제공할 수 있습니다. 다음은 동적 프로그래밍을 사용한 문제 해결 접근 방법입니다.

동적 프로그래밍 기본 개념

동적 프로그래밍(DP)은 큰 문제를 작은 문제로 나누어 해결하는 방법입니다. 이 문제에서도 우리가 목표 금액을 만들기 위해 각 금액을 만드는 데 필요한 최소의 동전 개수를 구하는 도중 중복된 계산을 줄일 수 있습니다. DP 배열을 사용하여 각 금액을 만드는 최소의 동전 수를 저장할 것입니다.

DP 배열 정의

dp[i]를 목표 금액 i를 만들기 위한 최소 동전 개수라고 정의합니다. 초기값으로 dp[0] = 0으로 설정하고, 다른 금액들은 INT_MAX(무한대)로 초기화합니다.

문제 풀이

이제 이론을 바탕으로 C++로 구현을 해보겠습니다. 코드는 다음과 같습니다:


#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    int N, M;
    cin >> N; // 동전의 종류 입력
    vector coins(N);
    for (int i = 0; i < N; ++i) {
        cin >> coins[i]; // 각 동전의 가치 입력
    }
    cin >> M; // 목표 금액 입력

    vector dp(M + 1, INT_MAX); // DP 배열 초기화
    dp[0] = 0; // 0원을 만들기 위해 필요한 동전 수는 0개

    // DP 배열 채우기
    for (int i = 1; i <= M; ++i) {
        for (int j = 0; j < N; ++j) {
            if (coins[j] <= i) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }

    // 결과 출력
    if (dp[M] == INT_MAX) {
        cout << -1 << endl; // 만들 수 없는 경우
    } else {
        cout << dp[M] << endl; // 최소 동전 개수 출력
    }

    return 0;
}

코드 설명

  • 먼저 필요한 라이브러리를 포함하고, 동전의 종류와 목표 금액을 입력받습니다.
  • 동전의 가치 정보를 담은 벡터 coins와 동전 개수를 저장할 배열 dp를 정의합니다.
  • dp 배열을 채우기 위해 이중 반복문을 사용합니다. 외부 반복문은 목표 금액을 순회하고, 내부 반복문은 동전의 종류를 순회하여 최소 동전 개수를 계산합니다.
  • 결국, dp[M]의 값이 INT_MAX이면 금액 M을 만들 수 없다는 의미이므로 -1을 출력하고, 그렇지 않으면 최소 동전 개수를 출력합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N*M)입니다. 여기서 N은 동전의 종류, M은 목표 금액입니다. 공간 복잡도는 O(M)로 DP 배열을 유지하기 위한 공간이 필요합니다.

마무리

이번 강좌에서는 C++ 코딩 테스트에서 자주 등장하는 ‘동전 개수의 최솟값 구하기’ 문제에 대해 동적 프로그래밍을 활용하여 해결하는 방법을 알아보았습니다. 이 문제를 통해 동적 프로그래밍의 기본 개념과 DP 배열을 활용한 해결 방법을 습득할 수 있었기를 바랍니다. 동적 프로그래밍은 다양한 문제를 해결하는 데 필수적인 기법이므로, 충분한 연습을 통해 이해도를 높여보세요! 다른 알고리즘 문제도 함께 풀어보며 실력을 키워나가길 바랍니다.

감사합니다!