kcits970   1년 전

문제를 풀면서 한가지 생각이 들어서 게시판에 글을 남겨봅니다.

1353번 문제에 다음과 같은 요구사항이 추가되었다고 가정해봅시다.

"첫째 줄에 리스트의 최소 크기를 출력하고, 그 다음 줄에 조건을 만족시키는 리스트를 아무거나 하나 출력하시오."

(S와 P의 값이 같은 경우는 답이 자명하기 때문에, S와 P가 다른 경우만 고려하겠습니다.)

서로 다른 S와 P, 그리고 2 이상인 자연수 N에 대하여 아래의 조건을 만족시키는 리스트 A = [a_1, a_2, a_3, ..., a_N]을 구성해야 합니다.

조건1: (sum of all elements of A) = S

조건2: (product of all elements of A) = P.

산술-기하평균 부등식에 의하여 (sum of all elements of A)/N >= (product of all elements of A)^(1/N)이고, 등호는 모든 원소가 같을 때 성립합니다.

따라서 A를 다음과 같이 구성하면, 조건1을 만족시키면서 원소들의 곱이 가장 큰 경우를 만들게 됩니다.

A = [S/N, S/N, S/N, ..., S/N] (N개의 원소가 모두 S/N으로 같은 경우입니다.)

따라서 만일 P가 (S/N)^N보다 크다면, 산술-기하평균 부등식에 어긋나므로 크기가 N인 해를 구성하는 것이 불가능합니다. (이하 P는 (S/N)^N 이하라고 가정하겠습니다.)

여기서 A의 원소를 적절히 바꿔서 조건2를 만족시키도록 할 수 있습니다.

A에서 2개의 원소를 고른 후, 하나의 원소에는 |ε| <= S/N을 만족시키는 ε를 빼고, 다른 원소에는 동일한 ε를 더합니다. 그러면 A는 다음과 같이 변형됩니다.

A = [S/N - ε, S/N + ε, S/N, S/N, ..., S/N]

ε을 뺐다가 더했기 때문에 원소들의 합은 변하지 않습니다. 변형된 A에서 원소들의 곱을 계산해보면 다음과 같습니다.

product of all elements of A

= (S/N)^(N-2) * (S/N - ε) * (S/N + ε)

= (S/N)^(N-2) * ((S/N)^2 - ε^2)

= (S/N)^N - ε^2 * (S/N)^(N-2)

따라서 적절한 ε을 선택하여 조건2를 만족시키도록 할 수 있습니다.

ε의 정확한 값은 ε에 대한 이차방정식 (S/N)^N - ε^2 * (S/N)^(N-2) = P을 통하여 구할 수 있습니다. (앞서 P가 (S/N)^N보다 큰 경우를 배제했기 때문에 방정식의 해는 항상 존재합니다.)

댓글을 작성하려면 로그인해야 합니다.