언어/c, c++

백준(BAEKJOOB)11047번 동전 0문제 c언어

깡 딱 2023. 1. 13. 20:43
728x90

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

문제를 이해하기 위해서 그리드 알고리즘을 공부하였다.

그리드 알고리즘에 대해 먼저 공부를 하고 문제를 푸는 것이 바람직하다.

 

이 문제를 해결하기 위해서는

1. 입력받을 케이스와 가격

2. 동전

3. 나머지 값들

 

이게 무슨 소리 인지는 차차 설명하겠습니다.

 

 

먼저 문제를 보고 10개를 받을 (cas)와 coin 값(4200)을 입력받아야겠다고 생각했고 

배열로 동전 값(저기 예시에 1 5,.. 50000) 들을 받아 저장하려고 하였다.

	int cas, coin;
	int a[10];
	scanf("%d %d", &cas, &coin);
	for (i = 0; i < cas; i++) {
		scanf("%d", &a[i]);
	}

 

 

 

여기서 무한 반복문을 만들어 주고 만약 입력받은 coin보다 a [n]이 크다면이라는 조건을 적어줍니다.

최솟값으로 구해야 하기 때문에

coin보다 수가 크다면 

다음 수로 넘어간다는 뜻이다

ex) coin=4200원이라면 50000이랑은 안 맞으니까 

n--되어 [9] 인덱스에서 [8] 인덱스에 있는 10000이 나오는 것이다. 순차적으로 [7] [6]..

while (1) {
	if (a[n] > coin) {
		n--;
	}
}

 

 

 

n은 cas-1이다 결국엔 아까 케이스가 10이라고 생각하면 9가 되는 것이다. 

사실상 위에 반복문들을 보면 0부터 9까지이다. 그러면 10개의 값을 받는 것이다.하지만

cas 그대로 넣게 된다면 a [10]이 되니까 10번째 수는 아무것도 없게 된다. 

우리가 저장한 배열에는 마지막 a [1]=1.... a [9]=50000의 수까지 저장되어 있기 때문이다.

그래서 밑에처럼 -1을 빼주는 것이다. 

	n = cas - 1;

 

 

만약 위에처럼 -- 되다가 coin보다 값이 작아지면 

coin값에 그 수를 뺸다

 

수로 예를 들면 coin(4200)이 a [n] 번째인 1000보다 크기 때문에

4200-1000을 해주면 3200이 나오게 된다. 이것을 반복하면 200원이 남고

count는 4번 올라가는 것이다.

 

이런 식으로 사이클이

돌아서 count를 올리고 

n = cas - 1;
	while (1) {
		if (a[n] > coin) {
			n--;
		}
        else if (a[n] <= coin) {
			coin = coin - a[n]; 
			count++;
            }

 

 

무한 반복문을 멈춰야 하기 때문에 4200이 0원이 되면 break 해줍니다. 

		if (coin == 0) {
				break;
			}

 

 

 

 

 

총 코드
#include<stdio.h>


int main(){
int cas, coin;
	int a[10];
	int sum = 0;
	int n = 0, i = 0;
	int count = 0;
	int tmp = 0;
	scanf("%d %d", &cas, &coin);
	for (i = 0; i < cas; i++) {
		scanf("%d", &a[i]);
	}
	n = cas - 1;
	while (1) {
		if (a[n] > coin) {
			n--;
		}
		else if (a[n] <= coin) {
			coin = coin - a[n];
			count++;

			if (coin == 0) {
				break;
			}
		}
	}
	printf("%d", count);
    }

 

 

이 코드를 통해 느낀 점 

coin = coin - a[n];
            
//ㅡㅡㅡㅡㅡㅡㅡㅡ
sum = coin % a[n]; 
tmp = coin / a[n];
count += tmp; 
tmp=tmp* a[n];
coin = coin - tmp;
            
// 이 두개의 코드는 
//같은 역활을 하지만 코드를 어떻게 쓰느냐에 따라
//가독성 차이가 많이 크다는 것을 알게 되었습니다

 

728x90