교재를 보다가 모르는 부분이 있어서 질문 드립니다.

  • KDH
    KDH

    30 페이지 를 보면 사탕 분배 문제가 있는데

    사탕의 최대 무게는 20이므로, 이때 사탕을 가장 많이 받은 어린이가 가장 적게 받은 어린이에게 사탕을 하나 준다고 해도 사탕의 총량이 역전되지 않습니다.
    그러면 이 둘이 가진 사탕의 양의 차이는 항상 감소합니다.
    이렇게 하면 항상 원래보다 더 공평한 답을 얻을 수 있기 때문에, 차이가 20 이상인 경우는 절대로 최적의 답이 될 수 없다는 것을 알 수 있지요
    따라서 넉넉잡아도 사탕을 가장 많이 받은 어린이가 20×N / 3+20 넘게 사탕을 받는 경우는 무시해도 됩니다.
    그러면 실제로 할당해야 하는 배열의 크기는 (20×N / 3+20)^3 ≤ 220^3(대략 1000만)으로 줄어듭니다.


    이 부분이 이해가 가질 않네요

    세명의 어린이에게 (219,191,190) 의 무게인 사탕을 분배 해준다고 가정하면 무게가 가장 큰 219 와 190은 차이가 20이 나니깐 이부분도
    최적의 답이 될수없는거 아닌가요?

    즉 궁금한건 실제로 할당해야하는 배열의 크기 (20×N / 3+20)^3 이
    왜 타당 한지가 궁금합니다.


    7년 전
8개의 댓글이 있습니다.
  • JongMan
    JongMan

    음 질문을 제가 명확히 이해했나 모르겠습니다만

    무게가 각각 219, 191, 190인 사탕 3개가 있을 때, 아이들에게 하나씩 나눠주면 최적이 아니냐? 라고 물어보신 거라면, 그 경우는 최적입니다. 하지만 이 문제에서 정해진 사탕의 최대 무게는 20이므로 이런 경우는 있을 수 없습니다. 사탕의 최대 무게가 2000 이라면 그에 맞춰 상태 공간 크기를 늘려야겠죠.


    7년 전 link
  • JongMan
    JongMan

    아직 이해가 안 가시거나 제가 질문을 잘못 이해했다면 다시 질문 주세요.


    7년 전 link
  • KDH
    KDH

    근데 교재에서는 가장 많이 받은 어린이가 20 * N / 3 + 20 넘게 사탕을 받는 경우는 무시해도 된다고 나와 있는데
    세 어린이의 사탕의 총량이 (180,190,200) 이면 가장 많이 받은 아이(200)와 가장 적게 받은 아이(180) 의 차이는 딱 20 이잖아요
    그래서 이 경우는 220이라는 범위내에서 총량이 맞는 경우라고 생각하는데

    제가 적은 (219 , 191 , 190) 라는 것은 사탕의 양으로 생각 했는데 적을때는 무게로 적었네요...
    그래서 가장 많이 사탕을 받은 어린이 (219)는 220이라는 범위 내에 있지만 가장 적게 받은 어린이(190) 과의 차이는 29 가 나니깐
    뭔가 좀 안맞는거 같다고 생각했는데 제가 어디서 부터 잘못 이해 한걸까요?


    7년 전 link
  • zzapcoder
    zzapcoder

    220이라는 범위는, 적절히 가지를 쳐낸 거라고 보시면 됩니다.

    가장 많이 받은 아이가 220이하 안에 있다고 다 답이라는것이 아니라,
    가장 많이 받은 아이가 220 넘게 사탕을 받는 경우는 절대 정답일수가 없다는 이야기입니다.

    그러므로 완전 탐색을 하기로 했을때 찾아야 되는 경우의 수가 너무 커서, 답이 확실히 아닌 경우를 이런 간단한 논리로 제거한거죠. 그러므로 이 경우는 "탐색 대상이지만 답은 아닌" 케이스라고 보시면 됩니다.


    7년 전 link
  • Being
    Being

    말씀하셨듯 (219, 191, 190)을 나눠주었다고 가정해 봅시다. 219만큼을 주기 위해서는 여러 사탕을 사용했을텐데, 그 사탕들은 모두 20 이하이므로 그것들 중 하나를 190에 주면 전체적으로 답이 더 좋거나 같아집니다. 따라서 위와 같은 경우는 답이 될 수 없습니다.


    7년 전 link
  • KDH
    KDH

    Being 님 그럼 답이 같아 질수 있기 때문에 이 경우 (219,191,190)은 답이 될 수 가 없다는 그런 의미 인가요??


    7년 전 link
  • Being
    Being

    답이 좋거나 같아진다고 한 것은 위의 예시와 관계없이 "가장 많은 사탕 더미"에서 "가장 적은 사탕 더미"로 임의의 사탕 한 개를 옮겼을 때 일어나는 일에 대한 것입니다. 바꾸면 대부분의 경우 답이 좋아지고, 답이 같아지는 경우는 이를테면 사탕 20짜리 5개가 있을 때 (40, 40, 20)과 같이 나누어준 경우 등 한정적입니다. 위의 경우는 답이 좋아지는 경우죠.


    7년 전 link
  • KDH
    KDH

    네 알겠습니다^^

    답변 감사합니다.


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