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

1. 본인 풀이

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

data.sort(reverse=True) # 동전의 금액을 내림차순으로 정렬

result = 1 # 결과(답)은 1부터 시작

while result <= sum(data): # 끝까지 답이 나오지 않으면 정답(최소값)은 '동전의 금액 총합 + 1'

    number = result

    for i in range(len(data)): # 동전의 금액 별로 반복

        if data[i] <= number: # 동전의 금액이 현재 값보다 작거나 같은 경우
            number -= data[i] # 일단 현재 값에서 동전의 금액만큼 뺀다

    if number == 0: # 동전의 금액 별로 전부 빼봤을 때 현재 값이 0 인 경우(만들 수 있는 금액인 경우)
        result += 1 # 다음 수로 넘어간다

    else: # 동전의 금액 별로 전부 빼봐도 현재 값이 0이 아닌 경우(만들 수 없는 금액인 경우)
        break # 그 값이 곧 정답

print(result)

2. 교재 답안

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

data.sort()

target = 1
for i in data:
    # 만들 수 없는 금액을 찾았을 경우 반복문 종료
    if target < i:
        break
    target += i

# 만들 수 없는 최소 금액 출력
print(target)

 

이 문제는 2번을 풀어봤지만 두 번 모두 1부터 시작하여 내부의 동전들로 만들 수 있는지 일일이 찾아가며 풀었다.

이렇게 풀이할 경우에는 1부터 가장 큰 값까지 찾아보는 반복문 한 개, 그 값을 가지고 동전 배열 내에 있는 값들을 모두 연산하는 반복문 한개로 2중 반복문을 사용하는 아주 비효율적으로 문제를 풀이하게 된다.

 

따라서 이 문제는 먼저 동전들을 오름차순으로 정렬한 뒤에 "target(다음 테스트 값)"을 설정하여 이 target 값이 해당 index의 동전보다 크거나 같은 경우에만 target 값을 업데이트 시켜가는 방식으로 쉽게 풀이 할 수 있다.

 

target-1 까지는 만들 수 있는 금액이라는 것이 증명되었기 때문에 다음 값으로 업데이트 시켜주고, 만약 이 target 값이 해당 index의 동전보다 작은 경우에는 그 금액을 만들 수 없다.