[python3] 이코테 - 만들 수 없는 금액 (ch.11 그리디 - 유형별 기출문제)

참고) 이것이 취업을 위한 코딩테스트다 with 파이썬 책을 기반으로 작성된 문제와 코드입니다. 
따라서 문제는 자세하게 적지 않고, 간단한 설명과 제 코드만 올리겠습니다.

 

만들 수 없는 금액 (ebook기준 p.513)

- N개의 동전
- N개의 동전으로 만들 수 없는 양의 정수 금액 중 최솟값을구하는 프로그램을 구하시오

##### 입력조건
- 첫쨋줄 동전의 갯수 N개 (1 <= N <= 1000 )
- 둘쨋줄, 화폐의 단위를 나타내는 N개의 자연수.화페의 단위는 1000000이하의 자연수

<1차시도 문제풀이>

우선 그리디 문제풀이에 대한 경험과 노하우가 없었기 때문에 어떻게든 풀어보자 하고, for문으로 때려박았다.
일단, 생각해낸 것은, '최솟값'을 구하는 것이기 때문에 숫자 두개로 더해서 나오는 숫자들만 비교하면 되지않을까? 였다. 하지만, 시간의 제한이 있는 코딩테스트 특성상 역시 내 코드는 제한시간 1초 내로 돌아가지 않고 매우매우 느려서 출력조차 안되는 코드가 되어버렸다. .. ㅋㅋㅋㅋ 시간복잡도 고려 안하는 하드코딩 전문가네 나...

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

def solution(n, money_type):
    
    result = []
    for i in range(0, n):
        for j in range(i+1, n):
            price = money_type[i] + money_type[j]
            result.append(price)
    result.sort()
    
    while True:
        for i in range(1, 10000000):
            if i in result:
                pass
            else:
                answer = i
                break
    return answer

solution(n, money_type)

 

<2차시도 문제풀이 : 정답코드>

##### greedy TIP!!
1. 최솟값을 구하는 문제는 무조건 for문을 돌릴게 아니라, 오름 차순으로 두고 작은 것부터 비교해가면서 풀어야한다.
2. 누적합과 화폐단위를 비교해가면서 구해본다. 화폐단위가 누적합 보다 클 경우, 그 사이에 갭이 존재한다는 뜻이다.

누적합을 for문으로 차근차근 구해나가면서, 숫자 1부터 비교해 나간다는 것이 포인트였다. 누적합보다 화폐단위가 클 경우에 그 사이에 만들 수 없는 수가 존재한다는 뜻임을 항상 기억하고 다음 그리디 문제에서는 꼭 적용해서 풀어봐야겠다.

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


def solution(n, money_type):
    money_type.sort()
    result = 1
    
    for money in money_type:
        if result < money:
            break
        result += money
    
    return result

solution(n, money_type)