백준 11047번 : 동전 0 #C

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

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

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

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

 

문제를 살펴보면 여러가지의 동전이 존재하는데, 이 동전들을 조합해서 동전의 개수를 최솟값으로 하여 가치의 합 K를 만들면 되는 문제이다.ㅎ

 

 

아무래도 문제자체가 이해하기 쉽고 구현하는데도 크게 사용되는 알고리즘이 없어 쉽게 답을 생각해 낼수 있었다.

 

 

핵심 포인트는 K를 구하기 위해서 동전의 가치가 큰 순서부터 내려오면서 K를 맞춰나가는 것이다.

 

#include <stdio.h>
#include <stdlib.h>
int main()
{
int n=0,k=0;
scanf("%d %d", &n, &k);
int *data = (int *)malloc(n * sizeof(int));

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

int cnt = 0;

for (int i = n - 1; i >= 0; i--)
    {
        if(k>=data[i])
        {
            cnt+=1;
            k-=data[i];
            i++;
        }
        if(k==0)
        {
            free(data);
            printf("%d", cnt);
            return 0;
        }
    }
    printf("%d\n", cnt);
    free(data);

    return 0;
}

 

 

먼저 n이 동전의 개수 k가 구하고 싶은 값이다.

처음에 동전의 가치 data배열을 만들때,  무작정 data[1000000]로 잡아버리는 안좋은 습관이 있었는데, 조금씩 동적 배열을 활용해서 입력에서 주어진 값의 배열만 만들어 성능을 향상시켜 나가고 있는 중이다.

 

 

동적배열이란!!

int *data = (int *)malloc(n * sizeof(int));

 

 

이 코드가 바로 동적배열로 문제에서 주어진 n개의 값을 저장할 수 있는 배열을 만든 코드이다.

프로그래밍 공부를 조금 해보았다면 배열은 포인터, 포인터는 배열이라는 말을 들었을 것이다.

배열 <->포인터

이 코드에서는 n을 입력받은 후 *data를 통해서 data가 n개의 int 자료형을 가지고 있는 배열로 만들어 낸것이다.

 

동적배열 하는 법 -> malloc ( 원하는 배열칸의 개수 * sizeof ( 원하는 자료형 ) ) 

 

 

이후 코드를 살펴보면 

 

for (int i = n - 1; i >= 0; i--)
    {
        if(k>=data[i])
        {
            cnt+=1;
            k-=data[i];
            i++;
        }

 

받은 동전의 뒤에서부터 (n-1)  <- 0부터 시작하기 때문에 n-1을 해주어야 합니다.

 

하나씩 줄여가면서 k값과 비교해서 k보다 작은 경우 차감을 해나가는 코드입니다.

 

초반부에서 얘기했듯이 동전의 가치가 큰 것부터 비교해가며 구하면 쉽게 최솟값을 구할 수 있습니다.

 

따라서 n-1부터 시작을 하였고 마지막 코드는 cnt 즉 필요한 동전의 개수를 출력하며 문제에서 요구했던 출력값을 구해내는 코드입니다.

 

  printf("%d\n", cnt);
    free(data);

 

추가적으로 동적배열을 하였기에 free(data) 를 통해서 메모리를 해제해주었습니다.

 

 

 

이 문제에서 배워가야할 사항들은

 

1. 동적배열 할당과 해제

 

2. 최솟값, 최댓값에 따른 반복구문 i,n의 시작점 파악

 

 

이렇게 2개가 있을 것 같습니다.