Partially Committed

오늘 다룰 주제는 Non-Constructible Value(Change) 이다. positive integer 로 구성된 array 가 주어졌을 때, 각각의 원소들의 합으로 나타낼 수 없는 최소의 값을 Non-Constructible Value 라고 정의한다. 예를 들어, coins 배열이 [1, 2, 5] 로 주어졌을 때 각각의 원소들로 만들어낼 수 있는 값은 1, 2, 3, 5 이므로 Non-Constructible Value 는 4 이다. 가장 먼저 떠올릴 수 있는 방법은 주어진대로 꾸덕꾸덕 구현하는 것이다. 주어진 배열을 ascending order 으로 sorting 한 다음에 모든 원소들의 합을 구한다. 그러면 Non-Constructive Value 는 1~max_sum+1 중 하나일 것이..