📑문제
동전의 갯수 N, 만들고 싶은 금액 K를 입력받는다.
그 후 N개의 동전의 가치가 오름차순으로 주어지고 K원을 만드는데 필요한 최소 동전의 갯수를 출력하라.
💡 핵심 포인트
1. 흐름
문제를 푸는 흐름 자체에 대해서 고민을 많이했다. 실버2 문제는 처음 풀어서 뭔가 어렵지 않을까 하는 생각부터 들었다. 큰 흐름을 먼저 잡으려고 생각을 했다.
일단 최소로 동전을 사용하기 위해서는 값에서 가장 크게 뺄 수 있는 값에서부터 시작해서 뺄 수 있는만큼 뺄셈을 하며, 동시에 Sum이라는 변수에는 값을 뺀 값을 그대로 더해가면서 Sum이 우리가 원하는 K값이 될때까지 반복문을 진행시키는 것으로 흐름을 잡았다.
1. N, K, 동전들을 입력받자
2. 동전 중에 뺄 수 있는(뺄셈을 해도 양수가 되는)최대값 동전을 찾자
3. Sum변수에 값이 우리가 찾는 K가 될때까지 필요한 동전이 최소로 드는 반복문을 반복한다.
2. 동전의 갯수가 가장 적으려면?
동전이 최소로 들기 위해서는 가장 큰 동전의 값부터 시작을 해서 빼야한다. 문제에서 동전의 갯수가 10개 이하라고 정해주긴 하지만 나는 동전의 갯수에 상관없이 진행을 해보고 싶어 최대값으로 가질 수 있는 동전을 찾았다.
//<-------최대값 코인찾기------->
for (int i = N - 1; i > 0; i--)
{
if (Coin[i] <= K)
{
Remit = Coin[i];
Re_index = i;
break;
}
}
3. 반복의 조건과 틀
이 부분도 나름 고민을 조금 했는데, 우리가 원하는 K 값이 Sum과 일치할 때까지 하는게 우리의 목표이지만 동전을 빼나갈수록 K에 값을 뺀다면 K값의 변동이 있기 떄문에 Target이라는 변수에 K값을 저장하고 Sum이 Target(K)의 값이 될때까지 진행을 하도록 하였다.
반복문은 K값에서 현재 Coin배열에 i번째를 빼도 양수가 되는 즉, 뺄 수 있는 경우에 진행을 하며 동전의 숫자인 Count를 ++, 그리고 K는 값을 빼주면서 진행하도록 하였다.
//<-----원하는 값과 일치할때까지---->
while (Sum != Target)
{
for (int i = Re_index ; i >= 0 ; i--)
{
if (i == -1)
i++;
while ((K - Coin[i]) >= 0)
{
Sum = Sum + Coin[i];
Count++;
K = K - Coin[i];
}
}
}🤦♀️틀린 이유🤦♂️
여러 번 VS에서 실행을 하고 백준에서 돌려서 틀리진 않았다. 실버4,5 문제는 그래도 얼추 15~25분? 정도면 푼 것 같은데 생각보다 시간이 조금 소요되긴 하였다.
🧾 전체 코드
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main()
{
int N;
int K;
int Coin[100];
scanf("%d %d", &N, &K);
int Remit = 0;
int Re_index = 0;
int Sum = 0;
int Count = 0;
int Target = K;
for (int i = 0; i < N; i++)
{
scanf("%d", &Coin[i]);
}
//<-------최대값 코인찾기------->
for (int i = N - 1; i > 0; i--)
{
if (Coin[i] <= K)
{
Remit = Coin[i];
Re_index = i;
break;
}
}
//<-----원하는 값과 일치할때까지---->
while (Sum != Target)
{
for (int i = Re_index ; i >= 0 ; i--)
{
if (i == -1)
i++;
while ((K - Coin[i]) >= 0)
{
Sum = Sum + Coin[i];
Count++;
K = K - Coin[i];
}
}
}
printf("%d", Count);
}
