백준 - 2309번(일곱 난쟁이)

문제 출처: https://www.acmicpc.net/problem/2309

문제

• 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

• 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

• 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

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

public class Main {

    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int[] heights = new int[9];

        for (int i = 0; i < heights.length; i++) {
            heights[i] = Integer.parseInt(reader.readLine());
        }

        Arrays.sort(heights);
        find(heights, new int[7], 0, 0, 0);

        System.out.println(sb);
    }

    // 조합!
    private static void find(int[] heights, int[] answer, int count, int sum, int start) {
        if (sum > 100) return;
        if (count == 7) {
            if (sum == 100) {
                sb.setLength(0);
                for (int n : answer) {
                    sb.append(n).append("\n");
                }
            }
            return;
        }

        for (int i = start; i < heights.length; i++) {
            sum += heights[i];
            answer[count] = heights[i];
            find(heights, answer, count + 1, sum, i + 1);
            sum -= heights[i];
        }
    }

}

• 조합을 활용하여 풀 수 있는 문제였다.
• 조건을 이용하여 빠르게 풀 수 있었는데, 여러 가지 경우가 가능한 경우 하나만 출력해야 하는 부분을 놓쳤다.
• 조건이 나올 때마다 StringBuilder를 초기화하여 가장 마지막의 경우가 출력되도록 하였다.