[백준(JAVA)] 2309번: 일곱 난쟁이

문제

✔ 난이도 - Bronze 1

설명

나는 조합(Combination)을 완전탐색하는 방법으로 9C7 사용
9명중 7명을 뽑아 그 합이 100이면 출력하고 아니면 다시 탐색

풀이 (9C7)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] arr = new int[9];
        for (int i = 0; i < 9; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        int[] result = new int[7];
        sub(arr, result, 0, 0);

        System.out.println(sb);
    }

    public static boolean sub(int[] arr, int[] result, int depth, int idx) {
        if (depth == 7){
            int sum = 0;
            for (int i = 0; i < result.length; i++){
                sum += result[i];
            }
            if (sum == 100){
                Arrays.sort(result);
                for (int i = 0; i < 7; i++){
                    sb.append(result[i] + "\n");
                }
                return true; //답 찾음. 끝!
            } else {
                return false;
            }
        }

        for (int i = idx; i < arr.length; i++){
            result[depth] = arr[i];
            if (sub(arr, result, depth + 1, i + 1)) {
                return true; // 하위 호출에서 조건 만족 -> 상위에서도 종료
            }
        }
        return false;
    }
}

근데 다른 사람들의 풀이를 찾아보니 9명 중 7명을 뽑는건 곧 9명중 2명을 뽑는 것과 같기때문에 9명중 2명을 뽑아 전체 합에서 뽑은 합을 뺐을 때 값이 100이라면 뽑은 그 2명이 난쟁이가 아니라는 로직으로 풀었다.
그럼 그 2명의 값을 0으로 바꿔주고 오름차순으로 정렬한 뒤, 배열의 index 2부터 8까지를 출력하면 답이라는 것이다.

나는 왜 이 생각을 못해냈을까.. 이런 역방향 사고는 문제를 더 많이 풀어보면서 감을 잡아야할 것 같다.

풀이 (9C2)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] arr = new int[9];
        int sum = 0;
        for (int i = 0; i < 9; i++){
            arr[i] = Integer.parseInt(br.readLine());
            sum += arr[i];
        }

        boolean flag = false;
        for (int i = 0; i < 8 && !flag; i++){
            for (int j = i + 1; j < 9; j++){
                if (sum - arr[i] - arr[j] == 100){
                    flag = true;
                    
                    arr[i] = 0;
                    arr[j] = 0;

                    Arrays.sort(arr);
                    break;
                }
            }
        }

        for (int i = 2; i < 9; i++){
            System.out.println(arr[i]);
        }
    }
}

TIL💡

📌 중첩 for문에서 안의 for문 내에서 break;를 하면 한 depth만 빠져나온다. 여전히 상위 for문은 돌게 됨. 따라서 flag를 세워 제어해주면 된다.