(C언어) 백준 11047 : 동전 0

문제 링크 : https://www.acmicpc.net/problem/11047

요즘 매운 맛이 땡겨서 백준에서 매운 맛을 찾고 있다. 요즘 천방지축으로 알고리즘에 들이대는 중인데, 그러다 눈에 걸린 그리디 알고리즘 챕터의 '동전 0' 문제를 풀었다. 이 문제의 아이디어는 2839번 문제를 풀며 얻었고, 2839번 문제를 푸는데는 이 포스팅이 도움이 되었다.

---

 

step 1. 평범한 배열 입력 구문이다.

step 2 . 사실상 본 문제의 정수.
입력한 코인을 기반으로, i = 인덱스를 내림차순으로 역배열한다.

높은 단가의 코인을 총액과 비교하여 최초 단가가 낮은 코인이 발견 될 때 마다 cnt에 값 추가.

코인의 단가가 총액보다 커질때 break 하여 while 탈출=> 인덱스 값을 낮춰 코인의 단가를 낮추고 다시 반복.

 

처음 푼 실버 3 문제라 뿌듯하다. 나는 맨날 천날 브론즈나 뒤적일 줄 알았지.
물론 아직도 머리가 지끈거리는 브론즈 1~2문제가 가득하다. 자만하지는 말자.

---

(코드)

#include <stdio.h>

int main() 
{
    int N, K;
    int cnt = 0;
    scanf("%d %d", &N, &K);
    int coin[11] = { 0, };
    for (int i = 1; i <= N; i++)
    {
        
        scanf("%d", &coin[i]);

    }
    for (int i = N; i >= 1; i--)
    {
        while (1)
        {
            if (coin[i] <= K)
            {
               K-= coin[i];    
               cnt++;
               
            }
            else
            {
                break;
            }
        }
    }
    printf("%d", cnt);
}