인프런 커뮤니티 질문&답변

안녕하세요^^

total 값이 홀수일때 만약 total = 13이고 sum = 6 이면 if(sum == total /2) 가 참이 되어버릴 수 있습니다. 그래서 미리 main에서 total 값이 홀수이면 바로 "NO"를 출력해버리면 위와 같은 일을 미리 방지할 수 있습니다. 이 내용에 대해서 영상은 수정보완하겠습니다.

아래 코드처럼 하시면 됩니다.

import java.util.Scanner;

class Main {
    static int n,total;
    static int[] array;
    static boolean flag;

    public static void main(String[] args) {
        Main T = new Main();

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        total =0;
        array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
            total += array[i];
        }
        if(total % 2 == 1) {
          System.out.println("NO");
          return;
        }
        flag = false;
        T.DFS(0, 0);
        if (flag) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    void DFS(int L, int sum) {
        if (L == n) {
            return;
        }
        if (sum == total / 2) {
            flag = true;
            return;
        }
        if (sum > total / 2) {
            return;
        }
        DFS(L + 1, sum + array[L]);
        DFS(L + 1, sum);

    }
}

안녕하세요, 인프런 AI 인턴입니다.
민표님, 소스코드를 잘 작성해주셨습니다. 다만, 적절한 종료 조건을 설정하지 않아 오답이 나올 수 있습니다. 재귀 함수 내에서 flag 값이 true가 되면 다른 모든 재귀 호출을 중단해야 합니다. 현재 코드에서는 flag가 true가 되더라도 모든 재귀 호출이 완료될 때까지 계속 실행됩니다. 이 부분을 수정해야 합니다.

DFS 함수 안에서 flag가 true가 됐을 때 바로 모든 재귀 호출을 종료하도록 코드를 수정해보세요. 이를 위해 void 대신 boolean을 반환 타입으로 하여, true를 받으면 바로 main 함수로 반환되게 해주세요.

다음과 같이 DFS 함수를 수정할 수 있습니다:

boolean DFS(int L, int sum) {
    if(flag) return; // flag가 true면 더 이상의 탐색을 중단
    if (sum == total / 2) {
        flag = true;
        return true; // 추가된 부분
    }
    if (L == n || sum > total / 2) {
        return false; // 추가된 부분
    }
    return DFS(L + 1, sum + array[L]) || DFS(L + 1, sum);
}

그리고 main 메소드 내에서 T.DFS(0, 0) 호출 시 boolean 반환값을 활용하세요.
기재해주신 코드에서 L == n 조건이 맨 처음에 나와야 하며, sum > total / 2 조건을 만족했을 때에 다른 경우의 수를 더 볼 필요가 없기 때문에 return을 해야 합니다.

만약 이렇게 수정해도 문제가 해결되지 않는다면 문제의 입력과 출력 조건을 다시 확인하거나 추가적인 조건이 있는지 검토해보세요. 문제의 요구사항을 정확히 충족시켰는지, 혹은 그 외의 논리적 오류가 없는지 점검하는 것이 중요합니다.