[ 문제 ]
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
입력
첫째 줄에 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
이 문제는 coins를 사용해서 k원을 만드는 데 필요한 동전 개수의 최솟값을 구하는 것이다.
여기서 n은 동전 종류의 개수를 의미하고, k는 만들어야 할 값을 의미한다.
① 처음 해야 할 일은 n, k를 입력받고, n의 개수만큼 동전 값들을 입력받아야 한다.
# N = 동전 종류 개수, K = 동전을 사용해서 만드는 합
n, k = map(int, input().split())
② 그래서 나는 동전 값들을 반복문을 이용해서 값을 입력받고, 리스트로 생성을 했다.
coins = [] # 동전 종류의 리스트 생성 선언
for i in range(n):
i = int(input())
coins.append(i)
coins.sort(reverse=True)- 앞서 입력받은 n의 길이만큼 반복문을 수행하고, 입력받은 값을 리스트로 추가하였다.
- 생성한 리스트를 내림차순으로 정렬시킨다.
③ 이제, 생성한 coins 리스트를 사용하여 k원을 만드는데 필요한 동전 개수를 구해보자.
- 나는 처음에 이 문제를 풀 때 coins 리스트를 어떻게 사용할까 생각하다가, 반복문을 이용해서 coins 리스트 안에 있는 요소들과 k 값을 비교해서 k값 보다 큰 요소들은 탈락시키고 다음 요소와 몫을 구하고 계산을 하고 동전 개수를 구하려고 했었다.
- 그래서 생각한 방법은 answer 이라는 변수를 만들었다.
answer = 0 # k원을 만드는 데 필요한 동전 개수의 최소 값answer 변수는 내가 찾아야 하는 k원을 만드는 데 필요한 동전 개수의 최소 값이다.
- 다음으로, 반복문을 생성하여 coins 리스트 안에 있는 요소들을 조사할 것이다.
for coin in coins:
if k >= coin:
answer += k // coin
k %= coin
if k <= 0:
breakcoins 안에 있는 수 중 k를 나눌 수 있는 가장 큰 수를 찾는 게 핵심이다.
coin 값보다 k 값이 크면 k와 coin을 나눈 몫을 answer에 더해준다.
그다음 나머지는 k에 부여한다.
이 과정을 반복하다보면 k값이 0이 되는 순간, break를 통해 반복문을 빠져나온다.
[전체 코드]
# N = 동전 종류 개수, K = 동전을 사용해서 만드는 합
n, k = map(int, input().split())
coins = [] # 동전 종류의 리스트 생성 선언
for i in range(n):
i = int(input())
coins.append(i)
coins.sort(reverse=True)
answer = 0 # k원을 만드는 데 필요한 동전 개수의 최소 값
for coin in coins:
if k >= coin:
answer += k // coin
k %= coin
if k <= 0:
break
print(answer)
