SRM 431 DIV2 1000P문제 질문드립니다~~

  • UNKI
    UNKI













    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.

    Definition

        


















    Class: SumAndProduct
    Method: smallestSet
    Parameters: int, int
    Returns: int
    Method signature: int smallestSet(int S, int P)
    (be sure your method is public)
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    12년 전
    13개의 댓글이 있습니다.
    • dgsquare
      dgsquare

      저도 1~2부를 왔다갔다 하는 편이라 한참을 보고 풀었는데요..
      문제에서 말하는 것은 최소의 수를 가지는 List의 요소가 정수가 아닌 경우도 있다느 것을 의미하고요. (사실 이것이 힌트져~)
      또 한가지 힌트를 드리자면,
      [spoiler="더 보기..."]합 S를 만족시키는 Element의 집합이 Element의 갯수에 따라 곱셈에서 어떤 특징을 가지는지를 생각해 보시면 됩니다. [/spoiler]


      12년 전 link
    • Being
      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]


      12년 전 link
    • UNKI
      UNKI

      dgsquare// 음...힌트를 보고도 해결책이 마땅히 떠오르지가 않아요~~~열심히 생각해 볼께요~~
      Being// 빙님 풀이는 깔끔하게 증명을...만 보고 일단 닫았습니다~~~~ -.-a 해결해보고 정 안되겠으면 보도록 할께요.


      12년 전 link
    • UNKI
      UNKI

      // dgsquare
      혹시 Element의 갯수가.....예를들어 S가 130이고 P가 117이라고 하면 1 13개와 117 한개로 나누어질 수 있다는 건가요??ㅡ.ㅡ;;


      12년 전 link
    • Being
      Being

      UNKI // 어.. 핀트를 살짝 잘못 잡으신 것 같아요 ㅠㅠ


      12년 전 link
    • Being
      Being

      [spoiler="힌트!"] 힌트를 하나 드릴게요. 만약에 답이 2인, 즉 2개의 원소 - a * (S - a) = P - 인 경우에 대해서, S가 상수여서 P가 a에 대한 함수식으로 나타내어진다고 상상해보세요. 즉 P = f(a) = a * (S - a) 라고 생각해 보세요. 이 때 나온 이차함수를 그래프로 그려 보세요. 그 이차함수를 구성하는 점들이 바로 가능한 P 값의 집합이겠지요? : )[/spoiler]


      12년 전 link
    • dgsquare
      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]


      12년 전 link
    • UNKI
      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]
      -_- 종이와 펜이 없다보니 여기서..죄송 -_-;;;


      12년 전 link
    • UNKI
      UNKI

      감사합니다!! 좋은 힌트가 됐어요!!


      12년 전 link
    • UNKI
      UNKI

      이런 좋은 방법이.....ㅡ.ㅡ.................나중에 최대 최소 나오면 꼭 써먹어야 겠네요~~


      12년 전 link
    • Being
      Being

      음.. 혹시 다른 분들 보실지 모르니 가려주세요 하하~[spoiler="더 보기..."]산술-기하평균 공식에서 등호조건이 성립하는 것이 각 변수가 같을 때이다 라는 사실을 알고 있다면 간단히 해결할 수 있었겠지요 : )
      [/spoiler]


      12년 전 link
    • UNKI
      UNKI

      ~_~예 고맙습니다~~~~~~


      12년 전 link
    • 김우현
      김우현

      우왕... 그걸 적용하시다니;;; 후덜덜 ㅠㅠ


      12년 전 link
    • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.