알고리즘 문제해결전략 1권 30쪽 사탕문제 질문

  • nuli
    nuli

    알고리즘 문제해결전략 1권 30쪽 사탕문제

    문제: N개의 사탕을 세명의 어린이에게 나눠줄 때,
    어린이들간 받은 사탕의 총 무게의 차이의 최소값은?

    여기에서 각 어린이가 받는 사탕의 무게를 기준으로 탐색한다고 했는데,
    구체적인 구현 방법이 어떻게 되는지 감이 오지 않습니다.

    즉, 맨처음 나온 방식대로 무식하게 완전탐색을 하면,
    각각의 경우의 수에 대해서 무게 차이를 계산하는 함수가 존재하기에 답이 바로 나옵니다.

    그런데, 각 아이가 받은 사탕의 무게가 예를들어 (100, 115, 120) 이라고 했을 때의 무게 차이는 바로 나오겠지만, 핵심은 주어진 사탕으로 위와 같은 분배가 가능한가 일텐데요,

    책에서는 그부분에 대한 설명은 없고 다만 개수가 중요한 게 아니라 무게가 중요하다 라고만 언급하고 있습니다.

    책에서 의도한 풀이가, (100, 115, 120) 같은 무게의 조합을 만들고 이 조합이 가능한 것인지를 체크하는 것은 아니죠? 이렇게 할 경우에는 뒷부분이 더 중요할 것 같은데요. 사탕을 하나하나 분배하며 무게를 늘려간다면 맨처음의 무식한 방식과 크게 차이가 없을 것 같구요.

    위와 같은 이유로, 복잡도를 계산하는 부분은 언뜻 이해가 가지만 그 복잡도 내에서 어떤식으로 구현이 가능한 것인지 모르겠습니다.
    알고리즘을 간략하게 기술해주시면 매우 감사하겠습니다.


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