[백준] 11047번 : 동전 0 [C/C++]

#문제

11047번: 동전 0

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

11047번: 동전 0

 

---

#접근방법

가장 높은 가치를 가진 동전부터 몇 개가 필요한지 구하면 되는 그리드 알고리즘을 사용하였다.

반응형

---

#풀이

#include <stdio.h>

int arr[10];

int main(){
    int n,k,ans = 0;
    int sum = 0;

    scanf("%d %d",&n,&k);

    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);

    for(int i=n-1;i>=1;i--){
        int cnt = (k-sum)/arr[i];

        ans += cnt;
        sum += cnt*arr[i];
    }

    ans += k-sum;

    printf("%d",ans);

    return 0;
}

 

문제에서 A1 = 1이라고 명시가 되어있기 때문에 무조건 가지고있는 동전으로 k원을 맞출 수 있다.

 

따라서 제일 가치가 높은 동전부터 순서대로 몇 개의 동전이 필요한지 구하면 되는 그리드 알고리즘을 사용할 수 있다.

 

n,k를 입력받고 n개만큼 arr[i]배열에 동전의 가치를 저장해준다.

 

n-1부터 1까지 반복문을 돌리면서 cnt = (k-sum)/arr[i]를 구해준다.

 

cnt의 의미는 해당 동전을 k금액이 넘어가지 않도록 최대한으로 쓴 동전의 개수이다.

 

ans에 cnt를 더해주고 sum에 cnt*arr[i]을 더해준다.

 

반복문이 끝나게 되면 ans에 k-sum을 더해주는데 이는 k금액을 맞추기 위한 1원 동전의 개수이다.

 

ans를 출력하면 정답이다.

---

#성능

---

#정리

A1 = 1이라는 조건을 보고 그리드 알고리즘을 생각하는 것,

 

이를 구현할 수 있는 구현력이 있으면 풀 수 있는 문제였다.