[백준] 14225번 : 부분 수열의 합 - JAVA [자바]

https://www.acmicpc.net/problem/14225

dfs 알고리즘 문제이다.

이 문제는 쉽지만 시간 초과를 신경써야 한다.

1. 자연수 1 부터 부분 수열의 합으로 만들 수 있는지 확인한다.
2. 또한 자연수를 만들 수 있는지 확인하면서 탐색한 부분 수열의 합들도 만들 수 있다는 표시를 해둔다.
3. 1 + 5 와 5 + 1의 합은 같다.

dfs 알고리즘을 코드로 보자.

public static void dfs(int sum, int num, int index) {
	answer[sum] = true;
    if (sum == num) {
    	answer[num] = true;
        return;
	}
    for (int i = index; i < N; i++) {
    	if (!visited[i]) {
        	visited[i] = true;
            dfs(sum + numArr[i], num, i + 1);
            if (answer[num]) break;
            visited[i] = false;
		}
	}
}

목표로 하는 자연수 num, 현재 부분 수열의 합 sum, 중복을 피하기 위한 index 를 넘긴다.

현재 부분 수열의 합 sum 은 만들 수 있는 수이므로 배열에 true 로 설정해준다.
또한 목표로 하는 num을 만들었으면 다음 자연수를 탐색하기 위해 종료한다.
중복을 피하기 위해 수열을 작은 수부터 정렬하고 난 뒤 탐색을 할 때 index를 넘겨준다.

public class bj14225 {

    public static int N;
    public static int[] numArr;
    public static boolean[] visited, answer;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        numArr = new int[N];
        answer = new boolean[2000001];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(numArr);

        int num = 1;
        while (true) {
            visited = new boolean[N];
            dfs(0, num, 0);
            if (!answer[num]) {
                bw.write(num + "\n");
                break;
            }
            num++;
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int sum, int num, int index) {
        answer[sum] = true;
        if (sum == num) {
            answer[num] = true;
            return;
        }
        for (int i = index; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(sum + numArr[i], num, i + 1);
                if (answer[num]) break;
                visited[i] = false;
            }
        }
    }
}