작성한 질문수 27

0

안녕하세요^^

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 인턴이에요. 코드를 확인해보니, 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; // 추가된 부분
        }
    }
}

이렇게 수정하고 실행해보세요. 이제 정상적인 결과가 나와야 할 거에요. 이해가 되지 않는 부분이 있다면 또 문의해주세요. 좋은 결과 있기를 바라며 화이팅하세요!