시간초과가 나는 부분이 조합부분이 맞네요
치킨집을 뽑으실때 시작하는 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; } } } }
위와같이 바꾸면 불필요한 치킨집 중복선택을 없애실 수 있습니다.
hik3562 4년 전
제가 생각한 로직은 다음과 같습니다.
2. M의 개수만큼 조합으로 경우를 뽑고
3. 집의 거리에서부터 M의 개수만큼 뽑은 값의 index를 치킨집의 정보를 저장한 ArrayList에 접근하여 값을 계산하고
4. 집의 거리마다 최소인 거리를 찾고 전체 값을 구한뒤
5. ans(출력 답) 을 갱신하였습니다.
시간초과 나는 부분이 조합이라고 생각했는데,
제가 뭐를 놓치고 있는지 궁금합니다. 감사합니다.