이코테 - [만들 수 없는 금액]

문제

• 동네 편의점의 주인인 동빈이는 N개의 동전을 갖고 있다. 이 때 N개의 동전을 이용해 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성해라.

입력

• 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다. (1 <= N <= 1,000)
• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 이 때, 각 화폐 단위는 1,000,000(백만) 이하의 자연수다.

출력

• 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력한다.

---

👀 처음 내 풀이

# 내 풀이(틀림)
N = int(input())
# coins=[]
coins = list(map(int, input().split()))

coins.sort()  # 작은 수부터 정렬
result = []

for i in range(len(coins)):  # 동전액수와, 동전 두개 합산해서 만들 수 있는 금액 리스트에 넣어주기
    result.append(coins[i])
    for j in range(i+1, len(coins)):
        num = coins[i] + coins[j]
        result.append(num)
# 동전 세개, 혹은 네개로 만들 수 있는 금액의 시간복잡도 n^3, n^4 -> 너무 크다..

result.sort()
result = list(set(result))  # 중복제거해주기

print(result)

처음에 풀이는 맨 처음 기존의 동전 1개로 만들 수 있는 금액을 result리스트에 넣고,

동전 갯수로 2개, 3개, 4개.. 등으로 만들 수 있는 경우를 나눠서 생각하여, 동전 갯수만큼 for문을 짜야겠다 했다. 하지만, 그럼 시간복잡도가 n^3, n^4이 넘어가기에 이렇게 푸는게 아니구나 깨달았지만 어떻게 접근해야 할지를 감이 오지 않았다. 

 

⚡ 풀이과정

 

동전을 오름차순 정렬한 뒤에, 1원부터 만들 수 있는지 하나씩 확인하는 과정을 거친다. 

전체적인 알고리즘은 다음과 같다.

• 현재 상태를 1부터 (target-1)까지 만들 수 있는 상태라 하고, target의 금액을 만들 수 있는 지를 확인한다.

1. 1부터 target을 시작하며, 만들 수 있는지 확인한다.
2. 해당 동전의 단위가 target보다 작을 경우 target은 만들 수 있는 금액이다.
3. target을 만들 수 있다면, target값을 해당 동전의 단위를 더한 값으로 업데이트 시켜준다.
4. 만들 수 없다면, 해당 target은 만들 수 없는 금액이므로, 그 값을 출력해준다.

 

 

❄ 정답

 

# 정답
n = int(input())
coins = list(map(int, input().split()))
coins.sort()

target = 1
for coin in coins:
    if target < coin:
        break
    else:
        target += coin
print(target)