[알고리즘] 백준 2309 일곱 난쟁이

수학에서의 조합의 개념을 이용해서 풀어야 하는 문제이다.

n C r = n-1 C r  +  n-1 C r-1

ex) 7 C 3 = 6 C 3 + 6 C 2 = 20 + 15 = 35

 

 

이 문제에서는 9 C 7 의 경우를 구하면 된다. 

 

그리고 각 계층의 경우에서 해당 번호를 뽑았는지 안뽑았는지 2가지의 경우의 수가 나뉘기 때문에 visited라는 9개의 빈 공간을 가진 visited[9] 배열에 체크가 필요하다.

 

각 계층에서 끝에 도달하여 9개가 모두 체크가 완료 되었을 때 해당 배열에서의 true 값들만 뽑아낸다면 전체의 경우를 모두 탐색할 수 있고 그 값들 중에서 조건식에 맞는 경우에만 출력을 한다면 알고리즘 완성이다.

 

package b2309;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static boolean finded = false;
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        //input information
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int [] arr = new int[9];
        boolean[] visited = new boolean[9];
        String inputString;

        for (int i = 0; i < arr.length; i++) {
            inputString = reader.readLine();
            String [] split = inputString.split(" ");
            arr[i] = Integer.parseInt(split[0]);
        }

        //logic
        comb(arr,visited,0,9,7);
        writer.close();
    }

    static void comb(int[] arr, boolean[] visited, int depth, int n, int r) throws IOException {
        if (r == 0) {
            printAnswer(arr, visited, n);
            return;
        }

        if (depth == n) {
            return;
        } else {
            visited[depth] = true;
            comb(arr, visited, depth + 1, n, r - 1);
            visited[depth] = false;
            comb(arr, visited, depth + 1, n, r);
        }
    }
    static void printAnswer(int[] arr, boolean[] visited, int n) {
        List<Integer> answer = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (visited[i])
                answer.add(arr[i]);
        }
        int sub = 0;
        for (int i = 0; i < answer.size(); i++) {
            sub+=answer.get(i);
        }
        if(sub == 100 && !finded) {
            answer.stream().sorted().forEach(v-> {
                try {
                    writer.write(v +"\n");
                    writer.flush();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            });
            finded=true;
        }
    }
}

 

 

 

! 한 개의 값이 아니라 여러개의 값이 답으로 나올 수 도 있다. 

필자는 그 경우를 제외하지 않아서 첫 번째 문제를 풀 때 틀렸다.

꼭 플래그 값을 설정하여 답이 한 번 출력되었으면 더이상 출력츨 하지 않도록 하자.