n개의 요소가 있는 코인이라는 배열이 있고 우리가 소유한 코인을 나타내는 배열이 있다고 가정합니다. i번째 코인의 가치는 코인[i]으로 표시됩니다. 값의 합이 x가 되도록 n개의 동전 중 일부를 선택할 수 있으면 값 x를 만들 수 있습니다. 0부터 시작하여 0을 포함하는 코인으로 얻을 수 있는 연속 값의 최대 수를 찾아야 합니다.
따라서 입력이 동전 =[1,1,3,4]와 같으면 출력은 10이 됩니다. 왜냐하면
-
0 =[]
-
1 =[1]
-
2 =[1,1]
-
3 =[3]
-
4 =[4]
-
5 =[4,1]
-
6 =[4,1,1]
-
7 =[4,3]
-
8 =[4,3,1]
-
9 =[4,3,1,1]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
목록 동전 정렬
-
답변 :=1
-
동전의 각 동전에 대해 수행
-
동전> ans이면
-
루프에서 나오다
-
-
ans :=ans + 동전
-
-
반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(coins): coins.sort() ans = 1 for coin in coins: if coin > ans: break ans+=coin return ans coins = [1,1,3,4] print(solve(coins))
입력
[1,1,3,4]
출력
10