[UVa 410] Station Balance | greedy

https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=351

Online Judge

• 1 <= C <= 5 개의 통이 있고, 각 통에는 0,1 혹은 2가지 시료를 담을 수 있다.
• 총 담아야 하는 시료의 수는 1<=S<=2C와 함께 각 시료의 질량을 나타내는 size S array M, M1, M2, ... ,Ms가 주어진다.
• 이때 IMBALANCE 값이최소가 되도록 하려면 어떻게 담아야 할까?
• 각 통에 담긴 질량의 평균을 A라고 할 때 IMBALANCE는 대충 A와 담긴 시료 질량의 분산이라고 생각하면 될 것 같다. ㅎ

사실 이렇게 증명하는 게 맞는건지는 모르게따. ㅇㅅㅇ
일단 해본다고 하긴 했는데 끝 마무리가 조금 이상한 느낌...

망할 시험

교수님 풀이를 들었는데 Greedy 를 solve 할 때 자신 없으면 일단 Sorting 하라고 하신다.

• S<2C일 때 2C-S개의 질량이 0인 시료를 가상으로 정의한 다음 이를 추가한다
  • 왜냐? ) 각 통당 2개의 시료씩 배치하고 싶은데 시료의 수량이 모자라기 때문에 이를 가상으로 추가하여 진행한다.
• 가상의 질량을 추가한 시료들을 정렬한 뒤 Mi와 Mn-i+1을 같은 통에 넣어준다.
  • {0, 0, 1 ,2 ,5 ,7} => {0,7}, {0,5}, {1,2}

이 solution은 항상 최적이다. 왜??

이게 제일 중요한데 이유를 알잘딱깔센 설명하기가 어렵다. 그치만 나에겐 구글이 있지.

뭔진 모르겠지만 일단 해보게. 땨

• 위의 예시처럼 {0,0,1,2,5,7}의 경우로 정렬 되어있는 경우에서 시작 해 보자
• 인접한 두 질량의 시료들을 묶어 하나의 통에 넣는다고 가정하자.

이렇게  진행하는 것이 맞을까?
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
맞겠지 뭥.

(+추가) 시험끝나고 다시 글 보니까 멀쩡한 증명이 1도 없다. ㅇㅅㅇ ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 깨작깨작 그려넣은 그림일 뿐 증명 되는 것 은 하나도 없는 매직...이래서 알응 망했나..여튼...그렇다.

오늘은 코드 구현에 의의를 두지 않고 알고리즘이 왜 맞는지에 대해서 생각해보는 시간을 많이 가져보고자 한다.
알응덕에 알고리즘 공부 왕창 하는 것 같네....
기분 안좋은데 좋은 그런 느낌 뭔지 아나 혹시...
여튼 그래...
뿅