[BOJ] 2309 일곱난쟁이 - JAVA

1. 문제

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

2309번: 일곱 난쟁이

---

2. 풀이

답 여부를 반환하는 함수를 만들어 재귀호출을 했다. 

7번째 반복이고 합계가 100이라면 true, 그 나머지는 false를 리턴했다.

나중에 한꺼번에 출력하기 위해 find[] 배열을 사용했다.

 

현재 idx부터 총 난쟁이의 인원수(9)까지 반복하고, 현재 idx를 포함해도 나머지에서 답을 찾을 수 있는지 확인한다. 그 중에 답이 있다면 true를 리턴하고 함수를 끝낸다.

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

public class BOJ_2309_일곱난쟁이 {
    static boolean[] find = new boolean[9];
    static int[] dwarfs = new int[9];

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

        for (int i = 0; i < 9; i++) {
            dwarfs[i] = Integer.parseInt(in.readLine());
        }

        Arrays.sort(dwarfs);

        findDwarfs(0, 0, 0);

        for (int i = 0; i < 9; i++) {
            if (find[i]) System.out.println(dwarfs[i]);
        }

    }

    public static boolean findDwarfs(int idx, int count, int sum) {
        if (sum > 100) return false;
        if (count == 7 && sum == 100) return true;

        for(int i=idx;i<9;i++){
            find[i] = true;
            if(findDwarfs(i+1,count+1,sum+dwarfs[i])) return true;
            find[i] = false;
        }
        return false;
    }
}

---

3. 결과