그리디
현재 상황에서 지금 당장 좋은 것만 고르는 방법

✅ 문제

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

입력 예시

5
3 2 1 1 9

출력 예시

8

➕ 문제 해설

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)
    

• 동전의 정보를 오름차순 정렬한다. 우선 target = 1 로 놓고 동전의 정보를 for문을 돌려 차례로 본다. 보고 있는 동전의 정보가 target보다 크면 target까지가 만들 수 있는 금액이다. 동전의 정보가 target보다 작거나 같으면 보고 있는 동전 정보를 target에 더하여 target 값을 업데이트한다.

1, 2, 3
target 1로 설정 -> 가능
+1
target 2로 설정 -> 가능
+2
target 4로 설정 -> 가능
+3
target 7로 설정 -> 불가능
=>7

1 1 2 3 9 
1로 설정 -> 가능
+1
2로 설정 -> 가능
+1
3로 설정 -> 가능
+2
5로 설정 -> 가능
+3
8로 설정 -> 불가능
=> 8

📝 정리

아이디어를 떠올리는 데 너무 어려웠던 문제...
이러한 유형의 알고리즘을 알고 있어야 풀 수 있는 문제같다.