8개의 댓글이 있습니다.
-
-
KDH -
근데 교재에서는 가장 많이 받은 어린이가 20 * N / 3 + 20 넘게 사탕을 받는 경우는 무시해도 된다고 나와 있는데
세 어린이의 사탕의 총량이 (180,190,200) 이면 가장 많이 받은 아이(200)와 가장 적게 받은 아이(180) 의 차이는 딱 20 이잖아요
그래서 이 경우는 220이라는 범위내에서 총량이 맞는 경우라고 생각하는데제가 적은 (219 , 191 , 190) 라는 것은 사탕의 양으로 생각 했는데 적을때는 무게로 적었네요...
그래서 가장 많이 사탕을 받은 어린이 (219)는 220이라는 범위 내에 있지만 가장 적게 받은 어린이(190) 과의 차이는 29 가 나니깐
뭔가 좀 안맞는거 같다고 생각했는데 제가 어디서 부터 잘못 이해 한걸까요?
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
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 이
왜 타당 한지가 궁금합니다.
10년 전