[그리디] 만들 수 없는 금액

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 14분

1. 문제 설명

- 다양한 금액들이 주어지고, 해당 금액들을 조합해서 만들 수 없는 금액 중 최소값을 리턴하는 문제

2. 접근 방식

-  처음에는 for문을 이용해볼까 고민을 하다가 인적성 공부를 하다 배운 조합이 생각이 났다.

- 조합이 경우 itertools라는 모듈 내에 combinations 함수가 있어 이를 활용하기로 했다.

3. 코드

from itertools import combinations

def find_money(x, ls):
    dp = [False]*sum(ls)
    answer = 0
    idx = sum(ls)
    for i in range(1, len(ls)):
        for j in list(combinations(ls, i)):
            dp[idx - sum(j)] = True
    for k in range(1, len(dp)+1):
        if dp[k] == False:
            answer = k
            break
    print(dp)
    return answer

4. 코멘트

- 확실히 모듈이나 함수 등을 알아두면 활용하기 좋은 것 같다. 사용법을 모르더라도 '어 이런 게 있었던 것 같은데...'라는 생각만으로도 문제에 더 수월하게 접근 할 수 있는 것 같다.

- 만약 combinations 함수를 몰랐더라면 level2 이상의 체감 난이도로 문제를 풀었을 것 같다.