[그리디] 04.만들 수 없는 금액 (유형별 기출문제, 이것이 코딩테스트다 with 파이썬)

그리디 개념

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
• '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기
• 다양한 알고리즘에 두루 사용    # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘

빈출유형

거스름돈 문제

• 거슬러 줘야 할 동전의 최소 개수 찾는 문제
• 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업

1이 될 때까지

• N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산
• 최대한 많이 나누기가 문제 해결 아이디어

 

문제

 

해설

정렬을 이용한 그리디 알고리즘

 

아이디어

화폐 단위 오름차순 정렬

1부터 차례대로 특정 금액 target 만들 수 있는지 확인

target을 만들 수 있으면, 값 업데이트

 

ex) 1, 2, 3, 8의 화폐

0. 처음에는 금액 1을 만들 수 있는지 확인하기 위해, target = 1로 설정.

1. target = 1을 만족할 수 있는지 확인. 1 동전 있으므로 target 1+1=2로 업데이트. (1까지의 모든 금액 만들 수 있음)

2. target = 2를 만족할 수 있는지 확인. 2 동전 있으므로 target 2+2=4로 업데이트. (3까지의 모든 금액 만들 수 있음)

3. target = 4를 만족할 수 있는지 확인. 3 동전 있으므로 target 4+3=7로 업데이트. (6까지의 모든 금액 만들 수 있음)

4. target = 7을 만족할 수 있는지 확인. 7보다 큰 8 동전 있으므로 7 만드는 법 없음. → 답 : 7

 

풀이

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    target += x
    
# 만들 수 없는 금액 출력
print(target)

 

해석

변수 : 동전 개수 N, 동전 종류 list, 동전합 target

 

1. 동전 개수 N, 동전 종류 list 입력받기

2. 동전 종류 정렬하기 : 오름차순

------------------------ 반복문 : 동전 종류 x in list  ------------------------

3. 동전합 target이 현재 동전 x보다 작으면 break

4. 동전합 target에 현재 동전 x을 더하기

-------------------------------------------------------------------------------------

5. 만들 수 없는 금액 출력