[백준] 11047번 동전 0

 

 

문제

소스코드

 

#include<iostream>
#include<vector>
 
int main() {
    int N{}, K{};
    std::cin >> N >> K;
 
    std::vector<int>coins;
 
    for (int i = 0; i < N; ++i) {
        int coin{};
        std::cin >> coin;
        if (coin <= K) //K 이상의 코인값은 받아봐야 의미가 없다.
            coins.emplace_back(coin);
    }
 
    int minSumCount{}, sum{}; 
    auto iter = coins.rbegin(); 
    while (sum != K) {
 
        if (*iter + sum <= K) { //현재 값+sum이 K보다 작다면 덧셈
            sum += *iter;
            minSumCount++;
        }
        else { //아니라면 코인 반복자 이동
            ++iter;
        }
    }
    std::cout << minSumCount << "\n";
}

 

후기

이 문제를 해결하기 위한 방법은 그리디 알고리즘이다.

그리디 알고리즘은 최적해를 구하는 데 사용하는 방법으로 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나아가는 알고리즘이다. 

 

문제는 어렵지 않다. 먼저 N만큼 값을 받아서 coins 컨테이너에 저장을 하는데 이때 나는 어차피 K보다 큰 coin들은 넣어봐야 의미가 없기 때문에 더 크다면 컨테이너에 삽입을 하지 않도록 하였다.

 

그 후 sum값이 K값과 동일할 때까지 반복문을 돈다. 현재 코인 컨테이너의 반복자(가장 높은 숫자)와 sum 값을 더했을 때 K보다 작거나 같다면 그 값을 더하고 그렇지 않다면 그다음 숫자로 이동을 하게 하면서 풀었다.

 

밤을 새고 와서 그런지 비교적 간단한 문제를 골라서 풀었다. 그리디 알고리즘 관련해서 많이 풀어보질 못했기 때문에 좀 더 난이도가 있는 문제도 풀어볼 예정이다.

해결하는데 걸린 시간: 6분

 

출처 및 레퍼런스

문제 링크: 11047번: 동전 0 (acmicpc.net)

 

관련 글

[온라인 코딩/그리디(Greedy)] - [백준] 5585번 거스름돈

[온라인 코딩/그리디(Greedy)] - [프로그래머스] 큰 수 만들기