[알고리즘] 백준 - 11047 ( 동전 0 )

문제

11047번 문제

접근

생각할점,  Ai = 1인 조건도 있어서 정답은 무조건 나와야한다

 

처음에 저는 while문에서 k > 0 인 동안에 k 값을 data 리스트 안에 넣어서 입력받은 n개의 종류들을 함께 정렬을 시키는 방식으로 하려고 했습니다. 하지만, 문제를 풀다 보니까 예제는 통과는 하는데 백준에서는 통과가 되지 않았습니다.

( 이유를 아시는 분은 알려주세요 ) ㅜㅜ

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

data = list()
for i in range(n):
    data.append(int(input()))

count = 0

while k > 0:
    data.append(k)
    data.sort()

    for i in range(len(data)):
        if data[i] == k:
            count += k // data[i-1]
            k -= (k // data[i-1]) * data[i-1]

print(count)

 

하지만 while문을 말고 배열에 있는 요소들과 k를 비교하는 다른 방법을 생각하다 보니까 배열을 reverse 시키고 역순으로 찾아보는 방법도 있었습니다. 따라서 반복문 안에서 k의 값이랑 가장 가까우면서 작거나 같은 요소를 찾아 count 값을 몫으로 증가 시키고 나머지 값을 k에 덮어 씌우는 방식으로 해결했습니다

1. 배열을 reverse 해서 역순으로 찾기
2. 배열안에서 k 보다 작거나 같은 요소중 가장 가까운 요소 찾기
3. count 값은 몫으로, k는 나머지 값으로 덮어 씌워서 반복하기

 

풀이

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

data = list()
for i in range(n):
    data.append(int(input()))

count = 0

data.sort(reverse=True)

for i in data:
    if k >= i:
        count += k // i
        k %= i
        if k <= 0:
            break


print(count)