n개의 수를 모두 더하면 s가 되는 수들을
모두 곱했을 때 최대가되는 집합을 구하라.
n은 1000이하
각각의 수들은 양수
s는 1억이하
수의 최소치 최대치를 구해서 탐색하고 오름차순의 경우만 본다는 가지치기도 했는데 시간안에 답을 못구해서 질문좀요.
어떻게 풀어야 하나요?
모두 곱했을 때 최대가되는 집합을 구하라.
n은 1000이하
각각의 수들은 양수
s는 1억이하
수의 최소치 최대치를 구해서 탐색하고 오름차순의 경우만 본다는 가지치기도 했는데 시간안에 답을 못구해서 질문좀요.
어떻게 풀어야 하나요?
s/n 으로 구성하는게 제일 크지 않을까요?
s/n의 내림과 올림으로 잘 합해서 만들면 됨
증명은 임의의 두 수의 차가 2이상인게 있으면 +1 -1 한 경우가 더 곱한 값이 커진다는걸 보이고, 두 수를 골랐을때 차가 2 미만인 경우가 단 하나밖에 나오지 않는다는걸 보이면 그게 최대가 됨