이것이 코딩테스트다 p314 만들수 없는 금액

Check Point !

( 해당사항 ✓체크 )

막힘 없이 수월하게 풀린 문제인가?

1시간이내로 풀렸던 문제인가? ✅
1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

시간을 써도 도무지 풀 수 없는 문제인가?

솔루션을 찾아봤는가? ✅

난이도 체감

최상

상

중

하 ✅

<이해도>

완벽히 이해 ✅

다소 헷갈리는 부분들이 있음

이해 못함

<덧붙일 말>
모든 경우의 수를 구하는 itertools 모듈 중

permutation 순열

순서 O , 중복 X : 자기자신 포함 X

dataset = ['A', 'B', 'C']

    printList = list(permutations(dataset, 2))
    print(printList)
    
    # 결과값
    # [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

dataset = ['A', 'B', 'C']

    printList = list(permutations(dataset, 3))
    print(printList)
    
    # 결과값
    # [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

combination 조합

순서 상관 X

  dataset = ['A', 'B', 'C']

    printList = list(combinations(dataset, 2))
    print(printList)
    
    # 결과값
    # [('A', 'B'), ('A', 'C'), ('B', 'C')]

dataset = ['A', 'B', 'C']

    printList = list(combinations(dataset, 3))
    print(printList)
    
    # 결과값
    # [('A', 'B', 'C')]

참고)

중복 순열

순서 O 중복 O : 자기 자신포함

dataset = ['A', 'B', 'C']

    printList = list(product(dataset, repeat = 2))
    print(printList)

    # 결과값
    # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]

permutation combination 차이와 사용방법을 다시 숙지하고,
sum함수 인지하기. tuple의 값이 여러개일때 sum함수를 다 더하지 못한다.
index함수 인지하기. index("원하는 값", "start값" , "end값")

---

문제

문제는 N개의 동전을 이용하여 만들 수 없는 금액 중 최솟값 구하기 .
ex )
n = 5
동전 3, 2, 1, 1, 9
일때 최솟값은 8

n = 3
동전 3 5 7
일때 최솟값 1

풀이

from itertools import *


n = int(input())
coins = list(map(int,input().split()))

arr = [0]* 1001

for i in coins:
    arr[i] += 1
    
for i in range(2,n):
    for j in list(combinations(coins,i)):
        total = 0
        for k in j:
            total += k
        arr[total] += 1

print(arr)
print(arr.index(0,1)) 

내가 푼 풀이는 O(N²)으로
모든 가능한조합 combination을 통해 구하고, 배열값에 +1을 통해 더해준후
0값이 있는 배열을 순번을 출력해주었다.

하지만 풀이 법을 봤을때 더 좋은 복잡도로 풀이를 하셨다. O(lgN) ?
고로 해당 풀이법을 다시 이해해 보자.

n = int(input())
ns = list(map(int,input().split()))


ns.sort()
target = 1

for i in ns:
    if target < i:
        break
    target += i

print(target)

그리디의 전형적인 문제인걸까..
최선의 선택으로 마지막 코인이 target값보다 크다면 break로 탈출하여 만들수없는 값을 출력하였다.

중간에 있는 값들이 왜 만들 수 있는가를 생각하기보다
그리디알고리즘이라고 조금 생각해보자.