문제
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 115659 | 60960 | 46959 | 51.965% |
문제 설명
준규가 가지고 있는 동전은 총 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
10 4200
1
5
10
50
100
500
1000
5000
10000
50000예제 출력-1
6예제 입력-2
10 4790
1
5
10
50
100
500
1000
5000
10000
50000예제 출력-2
12내 풀이
N, K = map(int,input().split())
N_list = list(int(input()) for i in range(N))
N_list.sort(reverse = True)
answer = 0
for x in N_list:
if K >= x :
answer += K//x
K = K%x
print(answer)백준 문제를 풀면서 가장 중요하게 파악해야 할 부분
=> 입력 받는 input값의 구조
만약 input 값이 1920번 문제처럼
5
4 1 5 2 3
5
1 3 7 9 5이렇게 들어오면 input()이 네번 들어온다는 뜻임! enter 한 개당 input 하나!
따라서 위 문제에서는 동전 종류 수인 N에 따라 input()를 받는 개수도 반복해서 달라지므로, input() for i in range(N) 이 구문을 활용해서 input를 반복해서 받아주어야 한다.
가장 적은 총 개수의 동전으로 주어진 금액을 구현하기 위해서는 가장 큰 금액의 동전의 개수를 최대화 하는 방향으로 계산해야한다. 따라서 N_list를 내림차순으로 sort 해준 뒤 하나씩 빼와서 나머지 값을 새로운 K값으로 지정하는 구문을 생각해봤다.
다른 풀이
N, K = map(int,input().split())
N_list = list(int(input()) for i in range(N))
answer = 0
for x in N_list[::-1]:
if K >= x :
answer += K//x
K = K%x
print(answer)위 처럼 N_list를 sort하는 방법 대신 기존 N_list이 오름차순으로 주어진다고 문제에서 명시되어 있기 때문에, N_list[::-1] 이 방식으로도 같은 표현이 가능하다.
-> 백준 문제는 input()값을 어떻게 split하고 어떻게 받느냐를 파악해야 하는게 중요할 것 같다 !!! (왜냐믄 이 문제에서 아래 구현하는 부분은 다 맞게 짰는데 위에 input부분에 오류가 있어서 한번 틀렸기 때문) 이거는 프로그래머스가 아닌 백준 문제를 얼마나 많이 푸느냐에 따라 점점 생기겠지 ..............
