알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 11. 그리디 - Q4. 만들 수 없는 금액

  • 0
  • 0
0
0

1. 만들 수 없는 금액

  • 난이도
  • 풀이 시간
    • 30분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128 MB
  • 출처
    • K 대회 기출

A. 문제

편의점 주인인 동빈이는 N개의 동전을 가지고 있다.
N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하라.

a. 예를 들면.

N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리 동전이라고 가정하자. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다.

N = 3이고 각 동전이 각각 3원, 5원, 7원이면, 만들 수 없는 양의 정수 금액 중 최솟값은 1원이다.

b. 입력 조건
  • 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N
    • 1 <= N <= 1,000
  • 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수, 자연수는 공백으로 구분
    • 각 화폐 단위는 1,000,000 이하의 자연수
c. 출력 조건
  • 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력.
d. 테스트 케이스
  • 입력 예시

    
    5
    3 2 1 1 9
    
    
  • 출력 예시

    
    8
    
    

B. 내 답안


n = int(input())  
array = list(map(int, input().split()))  
answer = []  
sum_ar = sum(array)  
for i in range(len(array)):  
    for j in range(i+1, len(array)+1):  
        answer.append(sum(array[i:j]))  

result = 1e9  
for i in range(1, sum_ar):  
    if i not in answer:  
        result = min(result, i)  
  
print(result)  
  
# 32분 53초 / Pass /

a. 회고

풀이

  • 어떤 방식으로 풀어야할지 몰라서, 동전들로 만들 수 있는 금액을 전부 구했다. 그리고 동전으로 만들 수 있는 최대값을 정한 다음 거기에 없는 최초의 수를 반환하였다.

반성

  • '시간복잡도 초과할지도 모른다.'라기보다는 더 효율적인 그리디적 풀이가 있다.

결론

  • 그리디에 대해 더 많이 풀어볼 것.

C. 문제 해설

정렬을 이용한 그리디 알고리즘으로 해결할 수 있다. 문제 해결을 위한 정확한 아이디어를 떠올리기 위해서는 충분히 고민을 해야 하는 문제이므로, 그리디 알고리즘에 익숙하지 않은 독자라면 문제 해결이 쉽지 않을 수 있다.

화폐 단위를 기준으로 오름차순으로 정렬한다. 이후 1부터 차례대로 특정한 금액을 만들 수 있는지 확인한다. 1부터 target-1까지의 모든 금액을 만들 수 있다고 가정하자. 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인하면 된다. 만약 target 금액을 만들 수 있다면, target 값을 증가시키는 방식을 이용한다.

그리디 알고리즘은 현재 상태에서 가장 좋아 보이는 것만 선택하는 알고리즘이다. 구체적으로 현재 상태를 1부터 target-1까지의 모든 금액을 만들 수 있는 상태라고 보자. 이때 매번 target인 금액도 만들 수 있는지(현재 확인하는 동전의 단위가 target 이하인지) 체크하는 것이다. 해당 금액을 만들 수 있다면, target의 값을 업데이트하면 된다.

다시 말해, 현재 값을 다 더한 것까지는 동전을 조합해서 만들 수 있다. 따라서 현재 값을 다 더한 것 + 1이 만들 수 없는 최솟값이다. 즉 다음에 더하는 값이 현재값의 합 + 1보다 크면 만들 수 없는 값이 나온다.

a. 책 답안

python-for-coding-test/4.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.