hik3562   4년 전

제가 생각한 로직은 다음과 같습니다.

  1. 입력 받을때 집, 치킨집을 구분하여 각각 ArrayList에 넣어줬습니다.

2. M의 개수만큼 조합으로 경우를 뽑고

3. 집의 거리에서부터 M의 개수만큼 뽑은 값의 index를 치킨집의 정보를 저장한 ArrayList에 접근하여 값을 계산하고

4. 집의 거리마다 최소인 거리를 찾고 전체 값을 구한뒤 

5. ans(출력 답) 을 갱신하였습니다. 

시간초과 나는 부분이 조합이라고 생각했는데,

제가 뭐를 놓치고 있는지 궁금합니다. 감사합니다.

ekdya93   4년 전

시간초과가 나는 부분이 조합부분이 맞네요

치킨집을 뽑으실때 시작하는 i가 nn부터로 되어있는데 저렇게 되면 불필요한 했던 탐색을 다시하게됩니다. 

다른부분 다 그대로 하고 dfs부분만

private static void DFS(int nn, int val ,int[] s) {
        if (nn == m) {
            int sum = 0;
            for (int i = 0; i < al2.size(); i++) {
                // 집 거리
                int temp = Integer.MAX_VALUE;
                for (int j = 0; j < s.length; j++) {
                    // 치킨 집 개수
                    if(temp>(abs(al.get(s[j])[0],al2.get(i)[0])+abs(al.get(s[j])[1],al2.get(i)[1])))
                        temp = (abs(al.get(s[j])[0],al2.get(i)[0])+abs(al.get(s[j])[1],al2.get(i)[1]));
                }
                sum += temp;
            }
            if (ans > sum)
                ans = sum;
            
            return;
        } else {
            for (int i = val; i < al.size(); i++) {
                if (visit[i] == 0) {
                    visit[i] = 1;
                    int temp = s[nn];
                    s[nn] = al.get(i)[2];
                    DFS(nn + 1,i+1, s);
                    s[nn] = temp;
                    visit[i] = 0;
                }
            }
        }
    }

위와같이 바꾸면 불필요한 치킨집 중복선택을 없애실 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.