알고리즘/문제풀이 - 백준

백준 15686 치킨 배달

문제 : https://www.acmicpc.net/problem/15686 서론 재귀를 이용한 완전탐색문제. 아이디어 2차원 배열을 만들지는 않고, 지도를 입력받을때 1이면 집 벡터에 좌표를 넣어주고 2면 치킨 벡터에 좌표를 넣어준다. 도시에 있는 치킨집 중 최대 M개를 골라서 가장 작은 도시의 치킨거리를 구해야하는데, 최대M개를 고르라고 해서 M개를 고르는 경우의 수, M-1을 고르는 경우의 수, M-2를 고르는 경우의 수 ....를 고려할 필요는 없이 M개를 고르는 경우의 수만 고려하면 된다. 치킨집이 M-1에 비해 M개면 수익이 감소할지는 모르나 우리는 치킨거리만 고려하면 되고, 치킨거리는 치킨집이 많을수록 당연히 작다. 그래서 도시에 있는 총 치킨집 중 M개를 골라야 하는데, 고를 수 있는 모든..

2019. 10. 5. 13:42