TSP 썸네일형 리스트형 1102번: 발전소 - Baekjoon Online Judge 외판원 문제(TSP: Traveling Salesperson Problem)로 대표되는 NP-난해에 해당하는 문제이다. 외판원 문제는 여러 도시가 주어졌을때 외판원이 도시별로 이동하는데 드는 비용이 각각 다른 경우 모든 도시를 다 돌고오는데 드는 비용을 어떻게 최소로 만들 것인지를 물어보는 문제이다. 외판원 문제 - 위키백과, 우리 모두의 백과사전https://ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C 발전소 문제도 이와 유사하다. 여러 발전소가 주어지고 발전소가 켜져있는 경우 그 발전소를 이용하여 다른 발전소를 켤 수 있고 그때의 비용은 각각 다르게 주어진다. 이때 최소한 켜져야하는 발전소의 숫자가 주어졌을 때 그 발전소 .. 이전 1 다음