그리디 04 만들 수 없는 금액

망할 이글루스 ㅠㅠ 열심히 쓰던걸 날렸다...

일단 수정한 코드부터..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

m = list(map(int, input().split())); n = len(m);   m.sort();   # 최소값 세팅 t = 1;   for i in m:   if i > t:     break;   # 지금까지의 합 + 새로운 화폐 까지가 커버할수 있는 최고임.   # 예를 들면 3이 추가된 상황에서는 3 + 2 + 1 (=6)다음 회전 때 최고값 + 1 을 넘는지 비교하면 됨. (처음에 1 부터 추가했던거 잊지말기)   t += i;  print(t);

cs

이 문제를 풀기 위해서는 아래와 같은 생각 방법이 필요하다.

새로운 화폐를 추가 했을 때 최대 어디까지 커버가 되는가?

다음 화폐 추가시 이전에 커버했던 최대값 + 1 을 만족하는가? (즉 중간에 구멍이 안 나는가?)

아래의 표를 통해 규칙을 알아보자.

3까지의세팅 

1	1
2	2
3	3
4	1이되는경우 + 3
5	2이되는경우 + 3
6	3이되는경우(1+2) + 3

단위 8 추가

1	1
2	2
3	3
4	4
5	5
6	6
7	-
8	8
9	1이되는경우 + 8
10 (이하생략)	2이 되는경우 + 8

 화폐가 추가될 때 신규 화폐가 이전에 가능했던 값 + 1 을 넘는지 보면 된다.