[코딩테스트 연습] 최고의 집합

 

문제: https://programmers.co.kr/learn/courses/30/lessons/12938

---

어떻게 풀지 오래 고민했던 문제입니다.

총합이 1억인 10,000개인 숫자를 모두 곱한 값을 구하는 시도 자체가

파이썬이 아닌 이상 불가능하다고 생각했습니다.

 

합을 직접 안구해도 알 수 있는 방법이 있나 생각해봤을 때,

곱하는 수의 차가 최소일 때 곱한 값은 최대가 됩니다. (아마 수학적으로 증명이 가능할텐데 그거까진 모르겠네요)

그래서 제곱, 세제곱, N제곱 형태가 되면 가장 베스트 케이스입니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43163.cc