프로젝트 EULER31 : 프로그램 솔루션 이해

Question

나는 해결책을 이해하려고 노력하고 있습니다 프로젝트 오일러 #31 포럼에서 찾았습니다.

문제는 다음 값을 가진 동전을 받는다는 것입니다.

coins=[1,2,5,10,20,50,100,200]

우리는 200에 도달하는 가능한 모든 방법을 생성하는 임무를 맡고 있습니다. 예를 들어, 10*10+100 = 200은 가능한 한 가지 방법이 될 것입니다.

1. 질문 2 : 아래 코드는 어떻게 작동합니까! 내 접근 방식에 비해 매우 우아하고 간단하며 간단 해 보이며 더 빨리 실행됩니다.

포럼을 탐색 하면서이 솔루션을 찾았습니다.

p_list = [1, 2, 5, 10, 20, 50, 100, 200]
case_num = [1] + [0] * 200
for i in p_list:
    for j in range(1, 201):
        if i <= j:
            case_num[j] += case_num[j-i]
print case_num[200]

첫 번째 줄은 동전 값 목록입니다. 두 번째 줄은 1과 200 0의 배열을 만드는 것입니다. 그러나 다음 네 줄은 나를 혼란스럽게했다. 나는 그것이 배열에서 가능한 방법의 수를 늘리고 있다고 생각하므로 Case_num [200]은 목록의 마지막 항목을 제공하지만 그것이 어떻게 작동하는지 전혀 모른다.

Answer 1

이것은 당신이 말했듯이 아주 좋은 해결책입니다. 코드는 각 동전 교단과 함께 1-200의 각 반복을 통해 자체적으로 구축됩니다.

Case_num 배열은 처음에 [1, 0, 0, 0, 0, 0, 0, 0, 0]으로 구성됩니다.

이 숫자 (초기 1을 제외하고)는 지금까지 반복 한 P_LIST의 코인을 사용하여 주어진 총계 (숫자의 색인으로 표시)까지 몇 가지 방법을 구축 할 수있는 방법입니다.

p_list의 첫 번째 코인은 1입니다. 따라서 1이 색인 내부에 들어갈 수 있다면 이전 인덱스의 값을 가져 와서 현재 인덱스에 추가합니다. 이것은 25로 알려진 5 가지 방법이 있고 크기 1의 동전을 찾았 기 때문에 26에 도달하는 5 가지 방법도 있습니다. .

따라서 1과 함께 반복 한 후에는 [1, 1, 1, 1, 1, 1 ... 1, 1]로 끝납니다.

이제 동전으로 올라갑니다. 이번에는 2의 동전을 사용하고 있습니다. 2가 색인보다 적은 경우, 현재 인덱스로 이전 인덱스로 이동하는 방법 수를 추가합니다.

예를 들어 2는 색인 1 내부에 맞지 않지만 인덱스 2에 맞지 않으므로 0에서 2로 이동하는 새로운 방법을 만들어 0으로 이동하여 현재 인덱스에 추가 할 수있는 모든 방법을 사용합니다. 인덱스 27에서 2는 색인 내에 적합하므로 25에 도달 할 수있는 방법 수를 가져 와서 27에 추가하십시오. 크기 2의 동전이 있다는 것을 알기 전에 27 명에 도달해야했습니다.

따라서 2와 반복 한 후에는 [1, 1, 2, 2, 3, 3, 4, 4 ...]로 끝납니다.

여전히 문제가있는 경우 전체 프로그램을 시도하고 걸어 갈 가치가있을 수 있습니다 (아마도 200 대신 총 50 개 감소).