[이코테] 그리디 - 만들 수 없는 금액 with 파이썬

JIN KANG·2022년 10월 6일

algorithm greedy python 이코테 코딩테스트

이코테

목록 보기

3/29

1. 문제

N , 동전의 개수가 주어진다.
뒤이어서 N개의 공백을 둔 문자열로, 화폐 단위가 들어온다.
주어진 동전으로 만들 수 없는 양의 정수 금액 중 최소값을 구하라.

입력 조건

동전의 개수 , 양의 정수 N ( 1 <= N <= 1000)
화폐단위는 1000000이하의 자연수

출력 조건

만들 수 없는 양의 정수 금액 중 최소값

입력 예시

5
3 2 1 1 9

출력 예시

2-1. 무지성 아이디어

답을 표시할 리스트 (최대크기 1000*1000000)를 만든다.
permutations로 조합을 만들어서 정답리스트에 표시한다. 아마 시간 초과할 듯..
작은수에서부터 탐색해서 표시안된 가장 작은 인덱스를 보여준다.

2-2. 저자 아이디어

화폐를 정렬해서, 만들 수 있는 값의 다음값을 target으로 설정하고 확인한다.
- 만들 수 있는 값의 다음값은, 초기에 1을 넣어두고, 화폐들을 더해나간다. ( 만들 수 있는 값의 다음 값 = 코드로는 초기에 1을 넣어두고, 화폐들을 누적한다 )
- 이것이 문제 설명과 구현코드의 괴리고, 이것이 코딩 공부를 괴롭힌다.
단, 화폐가 정렬되어 있고, 순서대로 있는 경우에, 화폐의 합의 의미가 그 값까지는 만들어진다는 것을 알아야 한다. ( 어떻게 처음부터 알 수 있나?? 다시 태어나야 하나? )

3-1. 예제 코드 (무지성 version)

1000개의 조합의 수는 약 50만개니까, 그걸 최대 1000번 반복문으로 돌리면..
당연히 시간초과 뜰 듯 하지만, 그냥 답보기 좀 그래서, 30분동안 뭐라도 했다.

## 입력 
N = int(input())
nums = list(map(int, input().split()))

## check_list 초기화
max_nums = sum(nums)
check_list = [0] * (max_nums+1)

## 조합 
from itertools import combinations

for i in range(1, len(nums)):
    for combi in combinations(nums, i):
        value = sum(combi)
        check_list[value] = 1
            
for i in range(1, len(check_list)):
    if check_list[i] == 0:
        print(i)
        break

3-2. 예제 코드 (저자 version)

# 입력 
N = int(input())
moneys = list(map(int, input().split()))

moneys.sort()  # 화폐를 오름차순으로 정렬 한다. 

# target 초기화 (현재까지 적산값의 다음 수)
# 이 수 앞까지는 만들 수 있고, 
# 이 수에 해당하는 수가 들어온다면, 만들 수 있는 수를 연장 할 수 있다. 
target = 1               
for money in moneys :
    if money > target :  # 만들 수 있는 수의 바로 다음 수까지는 들어오면, 만들 수 있는 수를 이어갈 수 있다. 
        break            # 그러나 그 수보다 더 큰 수가 들어오면, 이어나갈 수 없으니까, 못 만드는 수이다.  
    target+= money
    
print(target)