[백준] 11047번: 동전 0 (sol.6)

풀이시간: 32분

1. 나의 풀이

N, K = input().split(' ')
N = int(N)
K = int(K)

coins = [int(input()) for _ in range(N)]
coins.sort(reverse=True)

result = 0

while K > 0:
    for coin in coins:
        if K - coin < 0:
            continue
        else:
            K = K - coin
            result += 1
            break

print(result)

• 동전이 서로 배수관계임이 명시가 되어 있으므로 greedy로 접근
• 입력을 받고 int형변환
• 큰 단위부터 접근하기 위해 동전리스트를 내림차순 정렬
• 입력받은 금액이 0이 될때까지 큰 단위 코인부터 금액 차감 및 사용 갯수 +1
• 시간초과

N, K = input().split(' ')
N = int(N)
K = int(K)

coins = [int(input()) for _ in range(N)]

result = 0
i = -1

while K > 0:
    if K < coins[i]:
        i -= 1
        continue
    else:
        K = K - coins[i]
        result += 1

print(result)

• for문 없이 리스트 인덱스에 직접 접근하여 계산
• 리스트 뒤집기 연산 제거 및 -1 부터 접근
• 시간초과

N, K = input().split(' ')
N = int(N)
K = int(K)

coins = [int(input()) for _ in range(N)]

result = 0
i = -1

while K > 0:
    if K < coins[i]:
        i -= 1
        continue
    else:
        num = K // coins[i]
        K = K - (coins[i]*num)
        result += num

print(result)

• 작은 금액이 많이 쓰이는 경우가 있다고 생각이 듬
• 몫을 구해 한번에 차감하여 계산
• 통과

2. 또다른 풀이

N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]
coins.reverse()
ans = 0

for coin in coins:
	ans += K // coin
    K %= coin
	# print(f'coin: {coin}, K: {K}, ans: {ans}')
    # print를 찍어 중간중간 로그를 확인하는 것도 좋은 방법이다.

print(ans)

• map, split를 활용하여 한번에 형변환
• 큰 단위부터 차감해야되니 내림차순 정렬
• for문으로 큰 단위 코인부터 접근
• 입력 금액의 몫을 갯수로 저장 (주어진 금액을 넘는 코인은 몫이 0)
• 나머지를 다시 저장하여 다음 계산에 활용 (주어진 금액을 넘는 코인은 나머지가 그대로)

3. 보완할 것

• 계산을 한번에 해서 횟수를 줄일 수 있는 것을 생각
• map(func, iterable): iterable한 객체 안 전체 요소에 func을 적용할 때 활용
• 몫, 나머지의 연산의 존재를 되새기자.