알고리즘47 :: BOJ_15686_치킨배달

Code : 꽥! 클릭 클릭 해주세요.

lllilllilllilili/algorithmWithDonburi

궁금한게 생기시면 클릭해주세요!!! 서로 배워 가요 😀

꽥님의 오픈프로필

 

 

 

 

치킨 배달 문제는 두가지만 기억하고 있으면 접근하기 쉽습니다.

1) 치킨 집을 뽑을 수 = 조합

2) 그리고 맵의 크기만큼 순회하면서 집과 선택된 치킨집간의 거릿값을 모두 더해서 최솟값을 갱신하면 됩니다. 

 

조합은 재귀를 이용해서 구현할 수 있는데 

 

go(int next, int index) 라는 함수를 이용하여 조합을 구현하였습니다.

for(int i=index; i<al.size(); i++) {
                    int temp = ch[nn];
                    ch[nn] = i;
                    go(nn+1, i+1);
            }//조합 

 

를 이용하여 조합을 구현하였습니다. 

 

이후에는 맵의 크기만큼 순회하면서 for문 2번 사용, 집(=1) 그리고 치킨집 간의 거릿값을 모두 더해서 최솟값으로 갱신해주면 됩니다.