250P랑 500P는 엄청 쉬워서ㅡ,.ㅡ;; 자신감에 차 있었는데...
여기서... 시간 다 깎아먹네요 흙.....
저 아래....(Please note that the list may contain non-integer numbers) 부분이
자꾸 눈에 밟혀서 어떻게 풀어야 할지 떠오르지가 않습니다 ;ㅁ;
힌트라도 조금만 주시면 감사 ^^;;;
Problem Statement
A list of non-negative numbers is called satisfactory if the sum of the numbers in the list is equal to S and the product of the numbers is equal to P. Find a satisfactory list with the least possible number of elements, and return its size. If no such list exists, return -1 instead. Please note that the list may contain non-integer numbers.
저도 1~2부를 왔다갔다 하는 편이라 한참을 보고 풀었는데요..
문제에서 말하는 것은 최소의 수를 가지는 List의 요소가 정수가 아닌 경우도 있다느 것을 의미하고요. (사실 이것이 힌트져~)
또 한가지 힌트를 드리자면,
[spoiler="더 보기..."]합 S를 만족시키는 Element의 집합이 Element의 갯수에 따라 곱셈에서 어떤 특징을 가지는지를 생각해 보시면 됩니다. [/spoiler]
[spoiler="어.. 혹시 풀이를 보실 건가요?"]음.. 깔끔하게 증명을 해 보도록 할게요.
산술 평균과 기하 평균 사이의 관계식을 아시나요? 산술 평균은 (a_1 + a_2 + ... + a_n)/n 으로 정의된 값이고, 기하 평균은 (a_1 * a_2 * ... * a_n)^(1/n) 으로 정의된 값입니다.
이 두 식 사이에는 항상
(a_1 + a_2 + ... + a_n)/n >= (a_1 * a_2 * ... * a_n)^(1/n)
이라는 관계식이 성립합니다. 산술-기하 평균의 성질이죠. 등호 조건은 a_1 = a_2 = .. = a_n 일 때 성립합니다.
주어진 문제를 보니 합과 곱에 대해 다루고 있군요! 절묘하게도 일치할 수 있을 것 같습니다. 합 자리에 S를, 곱 자리에 P를 대응시키면 되겠군요.
S / n >= P^(1/n)
식을 정리하니 이렇게 됩니다.
(S / n)^n >= P
이 식이 의미하는 바는 무엇일까요? 우리가 어떤 n을 선택했을 때, 곱을 최대화하기 위해서는 모든 각 원소들을 같게 해야 합니다. (위의 등호 조건 참조) 그런데 위 부등식이 거짓이라면, 즉 모든 원소들을 같게 하여도 곱을 만들 수 없다면 n개로는 만들 수 없다는 뜻입니다. 반면, 위 부등식이 만족한다면 어떤 수열인지는 모르겠지만 만족하는 수열이 존재한다는 뜻이 되겠지요. 즉 n을 1부터 증가시켜 나가면서 저 부등식이 만족하면 존재하는 것으로 판정하면 되겠습니다 :)[/spoiler]
[spoiler="힌트!"] 힌트를 하나 드릴게요. 만약에 답이 2인, 즉 2개의 원소 - a * (S - a) = P - 인 경우에 대해서, S가 상수여서 P가 a에 대한 함수식으로 나타내어진다고 상상해보세요. 즉 P = f(a) = a * (S - a) 라고 생각해 보세요. 이 때 나온 이차함수를 그래프로 그려 보세요. 그 이차함수를 구성하는 점들이 바로 가능한 P 값의 집합이겠지요? : )[/spoiler]
물론 가능하긴 합니다면, 문제에서 요구하는 것은 최소의 갯수로 S,P를 만족시키는 것 이기 때문에, 14개로 나누는 것은 의미가 없습니다.
[spoiler="좀 더 쉽게 설명하자면.."]
Set이 1개의 요소를 가진다면 S =! P 일시 를 만족시키는 것은 없습니다. (두 수가 같아야만 1개의 요소로 표현 가능합니다. )
Set이 2개의 요소를 가진다면 합이 S가 될 때, P의 값의 범위는 0.0 ~ (S/2)^2 까지 가능합니다.
Set이 3개의 요소를 가진다면 합이 S가 될 때, P의 값의 범위는 0.0 ~ (S/3)^3 까지 가능합니다.
(이렇게 범위로 설정이 가능한 것은, 각 요소의 값이 정수가 아닌 실수도 가능하기 때문입니다. )
이런식으로 요소의 갯수 n을 늘려가며 P를 포함하는 범위가 올 때까지 확인하면 됩니다. :)
[/spoiler]
//Being 음~~~그렇다면
[spoiler="더 보기..."] f(a)는 원소의 갯수가 두개일때는 양수치역을 가지는
정의역이 0~s를 가지는 이차곡선이니까 최대값을 가지는 부분이 s/2가 되고
그렇게 되서 원소 두개일 때는 최대값이 S/2 * S/2 = (S/2)^2이 되는 것은 알겠습니다...그럼 원소 세개일 때는??
음~~~~ a * b * (S - a - b) = P'가 되나요?
그렇다면 여기서 a와 b의 최대값은 (dgsquare님 것을 보고 이해했음ㅡ.ㅡ;;) a == b여야 하니까...
a^2 * (S - 2*a) 의 최대값은 미분계수가 0인 곳이니까
f'(a) = 2*a * (S - 2*a) - a^2 * 2 = 0
-> 2 * (S - 2*a) = 2 * a
-> S - 2*a = a
-> S = 3*a
-> a = S/3
a=S/3 이고.... 대입하면...
= S^2 / (3^2) * (S - 2S /3) 니까
= S^2 / (3^2) * ( S/3)
= S^3 / (3^3) = (S/3)^3
이 최대가 되네요!! 간단한 규칙성으로 (S/n)^n이 P의 최대값이 되는군요 ~_~[/spoiler]
-_- 종이와 펜이 없다보니 여기서..죄송 -_-;;;
UNKI
250P랑 500P는 엄청 쉬워서ㅡ,.ㅡ;; 자신감에 차 있었는데...
여기서... 시간 다 깎아먹네요 흙.....
저 아래....(Please note that the list may contain non-integer numbers) 부분이
자꾸 눈에 밟혀서 어떻게 풀어야 할지 떠오르지가 않습니다 ;ㅁ;
힌트라도 조금만 주시면 감사 ^^;;;
Problem Statement
Definition
15년 전
13개의 댓글이 있습니다.
dgsquare
저도 1~2부를 왔다갔다 하는 편이라 한참을 보고 풀었는데요..
문제에서 말하는 것은 최소의 수를 가지는 List의 요소가 정수가 아닌 경우도 있다느 것을 의미하고요. (사실 이것이 힌트져~)
또 한가지 힌트를 드리자면,
[spoiler="더 보기..."]합 S를 만족시키는 Element의 집합이 Element의 갯수에 따라 곱셈에서 어떤 특징을 가지는지를 생각해 보시면 됩니다. [/spoiler]
15년 전 link
Being
[spoiler="어.. 혹시 풀이를 보실 건가요?"]음.. 깔끔하게 증명을 해 보도록 할게요.
산술 평균과 기하 평균 사이의 관계식을 아시나요? 산술 평균은 (a_1 + a_2 + ... + a_n)/n 으로 정의된 값이고, 기하 평균은 (a_1 * a_2 * ... * a_n)^(1/n) 으로 정의된 값입니다.
이 두 식 사이에는 항상
(a_1 + a_2 + ... + a_n)/n >= (a_1 * a_2 * ... * a_n)^(1/n)
이라는 관계식이 성립합니다. 산술-기하 평균의 성질이죠. 등호 조건은 a_1 = a_2 = .. = a_n 일 때 성립합니다.
주어진 문제를 보니 합과 곱에 대해 다루고 있군요! 절묘하게도 일치할 수 있을 것 같습니다. 합 자리에 S를, 곱 자리에 P를 대응시키면 되겠군요.
S / n >= P^(1/n)
식을 정리하니 이렇게 됩니다.
(S / n)^n >= P
이 식이 의미하는 바는 무엇일까요? 우리가 어떤 n을 선택했을 때, 곱을 최대화하기 위해서는 모든 각 원소들을 같게 해야 합니다. (위의 등호 조건 참조) 그런데 위 부등식이 거짓이라면, 즉 모든 원소들을 같게 하여도 곱을 만들 수 없다면 n개로는 만들 수 없다는 뜻입니다. 반면, 위 부등식이 만족한다면 어떤 수열인지는 모르겠지만 만족하는 수열이 존재한다는 뜻이 되겠지요. 즉 n을 1부터 증가시켜 나가면서 저 부등식이 만족하면 존재하는 것으로 판정하면 되겠습니다 :)[/spoiler]
15년 전 link
UNKI
dgsquare// 음...힌트를 보고도 해결책이 마땅히 떠오르지가 않아요~~~열심히 생각해 볼께요~~
Being// 빙님 풀이는 깔끔하게 증명을...만 보고 일단 닫았습니다~~~~ -.-a 해결해보고 정 안되겠으면 보도록 할께요.
15년 전 link
UNKI
// dgsquare
혹시 Element의 갯수가.....예를들어 S가 130이고 P가 117이라고 하면 1 13개와 117 한개로 나누어질 수 있다는 건가요??ㅡ.ㅡ;;
15년 전 link
Being
UNKI // 어.. 핀트를 살짝 잘못 잡으신 것 같아요 ㅠㅠ
15년 전 link
Being
[spoiler="힌트!"] 힌트를 하나 드릴게요. 만약에 답이 2인, 즉 2개의 원소 - a * (S - a) = P - 인 경우에 대해서, S가 상수여서 P가 a에 대한 함수식으로 나타내어진다고 상상해보세요. 즉 P = f(a) = a * (S - a) 라고 생각해 보세요. 이 때 나온 이차함수를 그래프로 그려 보세요. 그 이차함수를 구성하는 점들이 바로 가능한 P 값의 집합이겠지요? : )[/spoiler]
15년 전 link
dgsquare
물론 가능하긴 합니다면, 문제에서 요구하는 것은 최소의 갯수로 S,P를 만족시키는 것 이기 때문에, 14개로 나누는 것은 의미가 없습니다.
[spoiler="좀 더 쉽게 설명하자면.."]
Set이 1개의 요소를 가진다면 S =! P 일시 를 만족시키는 것은 없습니다. (두 수가 같아야만 1개의 요소로 표현 가능합니다. )
Set이 2개의 요소를 가진다면 합이 S가 될 때, P의 값의 범위는 0.0 ~ (S/2)^2 까지 가능합니다.
Set이 3개의 요소를 가진다면 합이 S가 될 때, P의 값의 범위는 0.0 ~ (S/3)^3 까지 가능합니다.
(이렇게 범위로 설정이 가능한 것은, 각 요소의 값이 정수가 아닌 실수도 가능하기 때문입니다. )
이런식으로 요소의 갯수 n을 늘려가며 P를 포함하는 범위가 올 때까지 확인하면 됩니다. :)
[/spoiler]
15년 전 link
UNKI
//Being 음~~~그렇다면
[spoiler="더 보기..."] f(a)는 원소의 갯수가 두개일때는 양수치역을 가지는
정의역이 0~s를 가지는 이차곡선이니까 최대값을 가지는 부분이 s/2가 되고
그렇게 되서 원소 두개일 때는 최대값이 S/2 * S/2 = (S/2)^2이 되는 것은 알겠습니다...그럼 원소 세개일 때는??
음~~~~ a * b * (S - a - b) = P'가 되나요?
그렇다면 여기서 a와 b의 최대값은 (dgsquare님 것을 보고 이해했음ㅡ.ㅡ;;) a == b여야 하니까...
a^2 * (S - 2*a) 의 최대값은 미분계수가 0인 곳이니까
f'(a) = 2*a * (S - 2*a) - a^2 * 2 = 0
-> 2 * (S - 2*a) = 2 * a
-> S - 2*a = a
-> S = 3*a
-> a = S/3
a=S/3 이고.... 대입하면...
= S^2 / (3^2) * (S - 2S /3) 니까
= S^2 / (3^2) * ( S/3)
= S^3 / (3^3) = (S/3)^3
이 최대가 되네요!! 간단한 규칙성으로 (S/n)^n이 P의 최대값이 되는군요 ~_~[/spoiler]
-_- 종이와 펜이 없다보니 여기서..죄송 -_-;;;
15년 전 link
UNKI
감사합니다!! 좋은 힌트가 됐어요!!
15년 전 link
UNKI
이런 좋은 방법이.....ㅡ.ㅡ.................나중에 최대 최소 나오면 꼭 써먹어야 겠네요~~
15년 전 link
Being
음.. 혹시 다른 분들 보실지 모르니 가려주세요 하하~[spoiler="더 보기..."]산술-기하평균 공식에서 등호조건이 성립하는 것이 각 변수가 같을 때이다 라는 사실을 알고 있다면 간단히 해결할 수 있었겠지요 : )
[/spoiler]
15년 전 link
UNKI
~_~예 고맙습니다~~~~~~
15년 전 link
김우현
우왕... 그걸 적용하시다니;;; 후덜덜 ㅠㅠ
15년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.