이 문제를 정확히 이해하지 못하겠습니다.
0은 공실 1은 가정집 2는 치킨집인데
가정집을 기준으로 각각의 치킨집의 거리를 하나씩 구한뒤에 각 가정집의 최소의 치킨거리를 구한뒤에 전부 더해주면 도시의 치킨거리의 최솟값이 나오는걸로 알고 있습니다.
저 또한, 가정집을 기준으로 모든 치킨집의 최소거리를 전부 구하는 방식을 문제를 해결하였는데
해설하고 다양한 블로그들의 해설을 보니 조합을 이용해서 풀어야한다고 하더라고요...
각 치킨집중에 M개를 임의로 골라 가정집과의 치킨거리를 구해야한다고 하는데... 저는 이게 이해가 안갑니다.. 왜 M개를 임의로 고르는건가요??
만약에 임의로 고른 치킨집 중에 가장 가까운 치킨거리를 납두고 둘다 먼 치킨거리를 구하게 된다면 그러면 치킨거리의 최솟값이 안나오는거 아닌가요??
예를 들어 [1,2,3,4,5] 5개중 3개를 임의로 고른다고 하면 [1,2,3],[1,2,4]... 이런 경우의 수가 나올텐데 이 경우를 다 계산해서 최솟값을 갱신해주기 때문에 막줄처럼 될일이 없음
아 그러면 가정집을 기준으로 5개의 치킨집이 있는데 그 치킨집을 3개를 조합으로 이용하면 모든 경우의 수가 나오기에 최솟값이 계속 갱신되는 것인가요??
ㅇㅇ 그중 한개만 뭐 랜덤하게 고른다는 개념이 아니라 진짜 그 조합에 대해 다 해보는거임
근데 진짜 궁금해서 그러는데 코드보여줄수 있음? 나는 본문봐도 조합밖에 방법이 안 떠오르는데..
임의로 살릴 치킨집을 조합을 이용해서 해결할 수 있습니다 이때 임의의 1회만 치킨집을 정하는게 아니라, 모든 조합의 경우를 다 따져봐서(브루트포스) 그 모든 경우 중 최솟값인 경우를 답으로 정하는겁니다 치킨집이 4개고, 치킨집을 각각 (1,2,3,4) 라 하고, 치킨집을 2개 살린다 했을 때
(1,2), (1,3), (1,4), (2,3), (2,4), (3,4) 의 모든 조합을 고려하게 되므로 이중에 정답이 반드시 있습니다. naive하게 모든 상황을 다 고려한 방법입니다
아하 모든 경우의 수를 고려하는것이네요.. 근데 이게 모든 치킨집의 수의 최소거리를 구하는것보다 효율적인가요??
치킨집이 4개면 총 가정집을 기준으로 4개의 최소거리를 구해주는 것인데 조합을 고려하면 6개의 최소거리를 구하는것이기에 비효율적인거 아닌가요??
하지만 치킨집갯수 M <= 13이니 시간제한 내에는 충분히 돌아가겠네욤
님이 생각하신 발상이 더 효율적이네요 다만 조건에 따르면 치킨집 수가 브루트포스 돌릴 수 있을 정도로 적어서 조합 일일이 따져줘도 풀려요
혹시 구체적으로 어떻게했는지 궁금한데 해당 소스코드 볼 수 있을까요
아직 코드는 만들지 않았습니다.. 지금 슈도코드도 작성안해서...
앗... 나도 본문에 "가정집을 기준으로 모든 치킨집의 최소거리를 전부 구하는 방식을 문제를 해결하였는데" 적혀있길래 아무리 생각해도 저렇게 하면 답 안나올거 같아서 물어봤는데.. 못 푸셨던거군
만약 풀렸다면 반례가 있을 것 같았음