-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
바둑대회 질문드립니다.
23.07.21 10:38 작성 조회수 182
0
이처럼 코드를 작성했는데 마지막 테스트 케이스 답이 0이 나옵니다. 어디가 잘못된건지 모르겠습니다.
import java.util.*;
import javax.security.auth.Subject;
import java.awt.List;
import java.io.*;
class Main {
public static int n,answer=10000000;
public static boolean[] visit;
public int solution(int[][] cans){
n=cans.length;
visit = new boolean[n];
dfs(0,0,cans);
return answer;
}
public static void dfs(int L, int s, int[][] cans) {
if(L==n/2) {
ArrayList<Integer> a =new ArrayList<>();
ArrayList<Integer> b =new ArrayList<>();
for(int i=0; i<n; i++) {
if(visit[i]) a.add(i);
else b.add(i);
}
int sum1=0,sum2=0;
for(int i=0; i<L; i++) {
sum1+=cans[a.get(i)][0];
sum2+=cans[b.get(i)][1];
}
answer = Math.min(answer, Math.abs(sum1-sum2));
}
else {
for(int i=s; i<n; i++) {
visit[i] = true;
dfs(L+1, i+1, cans);
visit[i] = false;
}
}
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution(new int[][]{{87, 84}, {66, 78}, {94, 94}, {93, 87}, {72, 92}, {78, 63}}));
System.out.println(T.solution(new int[][]{{10, 20}, {15, 25}, {35, 23}, {55, 20}}));
System.out.println(T.solution(new int[][]{{11, 27}, {16, 21}, {35, 21}, {52, 21}, {25, 33},{25, 32}, {37, 59}, {33, 47}}));
}
}
답변을 작성해보세요.
0
김태원
지식공유자2023.07.23
안녕하세요^^
answer 를 static 전역으로 잡아서 앞전 테스트 케이스의 answer를 그대로 유지하면서 다음 테스트 케이스를 실행하기 때문입니다. 아래 처럼 solution에서 매번 answer를 초기화해야 합니다.
public int solution(int[][] cans){
answer = 10000000;
n=cans.length;
visit = new boolean[n];
dfs(0,0,cans);
return answer;
}
0
인프런 AI 인턴
2023.07.23
안녕하세요, 인프런 AI 인턴이에요. 코드를 확인해보니, dfs 함수에서 L이 n/2와 같은 경우에만 a와 b에 숫자를 나누고, sum1과 sum2를 계산하고 있네요. 그러나 L이 n/2와 같아지기 전에 이미 재귀 함수가 끝나버리는 오류가 있습니다.
dfs 함수에서 for문을 돌리면서 visit[i]를 true로 바꾸고 재귀 호출을 하고 있는데, 재귀 호출 후에 visit[i]를 false로 바꾸지 않고 있습니다. 따라서 이전 단계에서 true로 바뀐 visit[i]가 그대로 남아서 올바른 결과를 얻을 수 없게 됩니다.
해결책은 dfs 함수의 마지막 부분에 visit[i]를 false로 바꾸는 코드를 추가하는 것입니다. 아래는 수정된 코드입니다.
public static void dfs(int L, int s, int[][] cans) {
if(L==n/2) {
ArrayList<Integer> a =new ArrayList<>();
ArrayList<Integer> b =new ArrayList<>();
for(int i=0; i<n; i++) {
if(visit[i]) a.add(i);
else b.add(i);
}
int sum1=0,sum2=0;
for(int i=0; i<L; i++) {
sum1+=cans[a.get(i)][0];
sum2+=cans[b.get(i)][1];
}
answer = Math.min(answer, Math.abs(sum1-sum2));
}
else {
for(int i=s; i<n; i++) {
visit[i] = true;
dfs(L+1, i+1, cans);
visit[i] = false; // 추가된 부분
}
}
}
이렇게 수정하고 실행해보세요. 이제 정상적인 결과가 나와야 할 거에요. 이해가 되지 않는 부분이 있다면 또 문의해주세요. 좋은 결과 있기를 바라며 화이팅하세요!
답변 2