https://www.acmicpc.net/problem/15686
결론부터 말하자면 아직 못풀었다..
2-3시간을 투자했는데도 안풀려서 잠시 내려놓고 좀 더 성장해서 다시 풀어볼 것이다
내가 시도했던 방법들은 이러하다
1. 각 치킨집이 모든 집까지의 치킨거리의 합을 가지고 있는다.
이 치킨거리의 합이 낮은 순서대로 순위를 매긴다
-> 실패 이유 : 치킨거리의 합이 같은 경우가 있음
2. 각 치킨집이 모든 집까지의 치킨거리의 합을 가지고 있고, 각 집으로부터 투표도 받는다.
이 투표수가 높은 것부터, 투표수가 같다면 치킨거리의 합이 낮은 것부터 순위를 매긴다
-> 실패 이유 : 아마 투표수도 같고, 치킨거리의 합도 같은 경우가 존재하는 것 같다
-> 예제는 모두 잘 출력되었는데 아쉽다..
위 과정을 거치고 나서,
각 집은 자신이 기억하고 있던 가장 가까운 치킨집이 폐점되었으면
다시 가까운 치킨집을 찾도록 했다.
그리고 나서 모든 치킨 거리의 합인 도시의 치킨 거리를 구하였다.
예제는 잘 출력되었어도 알고리즘에 흠이 있기 때문에 다시 풀어봐야할 것 같다.
다른 블로그를 살짝 보니까 조합을 사용하는 듯 했다.
생각지도 못한 방법이어서 부족함을 느꼈다..ㅠ
Game Programmer