알고리즘

[BOJ] 11047 동전 0

졔졔311 2023. 6. 6. 03:43
728x90
반응형

https://www.acmicpc.net/problem/11047

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

greedy

 

---------------------------------------------------풀이----------------------------------------------------

 

동전의 가치가 큰 것부터 사용해 K를 만들 때까지 그리디하게 동작하도록 하였다.

동전의 가치가 A1 = 1 이고,

A3 = A2의 배수, A4 = A3의 배수, ... 이기 때문에 그리디하게 풀린다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <map>

using namespace std;

int Ai[1'000'001] = {0, };

// N종류의 동전을 최소로 사용해 가치를 K로 만들어라.
int main(void){
    FASTIO;
    int N, K;
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> Ai[i];
    }
    // Greedy
    int answer = 0;
    for(int i = N-1; i >= 0 && K > 0; i--){
        while(Ai[i] <= K){
            K -= Ai[i];
            answer++;
        }
    }
    cout << answer << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

문제 조건에 나온 A1=1, Ai = Aj의 배수(i = j+1)라는 내용 때문에 그리디로 풀 수 있다.

이 조건을 보지 못했을 때에는 Ai의 최대 크기를 보고 dp를 떠올렸지만,

너무 급격하게 난이도가 상승한다고 생각해 문제를 꼼꼼히 보고 저 조건을 다시 발견하여 금방 풀 수 있었다.

728x90
반응형