[백준 2390번 / Java] 일곱 난쟁이

이 문제를 풀기 위해 완전탐색 알고리즘에 대해 공부하게 됐다.

반복문으로 하나하나 구현하는건 알겠는데 순열/조합의 재귀 방식이 너무 생소했다..

관련 문제들을 많이 풀어보면서 익혀야겠다!

 

순열에서는 비트마스크를 이용해 방문 표시를 하는게 특징인 것 같고 이 문제와 같이 조합에서는 방문 확인 대신 start 값을 하나 증가시켜주면 된다. 

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

public class Main{
    static int N = 9;
    static int[] input = new int[N];
    static int R = 7;
    static int[] password = new int[R];
    static int count = 0;
    static boolean flag = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(br.readLine());
        }
        comb(0, 0);
    }

    private static void comb(int cnt, int start){
        if(cnt == R) {
            if(100 == Arrays.stream(password).sum() && !flag) {
                Arrays.sort(password);
                flag = true;
                Arrays.stream(password).forEach(n -> System.out.println(n));
                return;
            }
            count++;
            return;
        }
        for(int i = start; i < N; i++) {
            password[cnt] = input[i];
            comb(cnt + 1, i+1);
        }
    }
}