백준 - 일곱 난쟁이(Java) 다시 풀기

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

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

[문제 설명]

완전탐색 문제입니다. 완전탐색을 처음 접했을 때 많이 헤멨던 문제라 다시 풀어보기로 했습니다.

 

[접근 방법]

9명 중 2명은 난쟁이가 아니다.

따라서, 두명의 키를 뺐을 때, 키의 총합이 100이면 그 두사람이 난쟁이가 아니다.

조합이므로 복잡도는 9C2 -> 36회 연산됩니다. 

 

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


public class HwangInGyu {
    static final int cntOfPeople = 9;
    static final int cntOfDwarfs = 7;
    static final int maxLength = 100;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 존재하는 높이인지 확인
        boolean[] isExistHeights = new boolean[maxLength+1];
        // 모든 생명체의 키
        int[] heightOfPeople = new int[cntOfPeople];
        // 가짜 드워프의 키
        int[] heightOfFalseDwarf = new int[cntOfPeople-cntOfDwarfs];
        // 현재 모든 생명체의 키의 총합
        int currentSumOfHeight = 0;
        for (int i = 0; i < cntOfPeople; i++) {
            int height = Integer.parseInt(br.readLine());
            heightOfPeople[i] = height;
            currentSumOfHeight += height;
            isExistHeights[height] = true;
        }

        // 가짜 드워프의 키를 구함.
        heightOfFalseDwarf = getFalseDwarfsIndex(heightOfPeople, heightOfFalseDwarf,currentSumOfHeight, 0, 0);
        if (heightOfFalseDwarf != null) {
            for (int i = 0; i < heightOfFalseDwarf.length; i++) {
                isExistHeights[heightOfFalseDwarf[i]] = false;
            }
            for (int i = 0; i < isExistHeights.length; i++) {
                if (isExistHeights[i]) {
                    System.out.println(i);
                }
            }
        } else {
            System.out.println(-1);
        }
    }

    // 가짜 드워프들의 키를 반환하는 메서드
    private static int[] getFalseDwarfsIndex(int[] heightOfPeople, int[] heightOfFalseDwarf, int currentSumOfHeight,int cntOfCurrentFalseDwarf, int idxOfPeople) {
        if (cntOfCurrentFalseDwarf == cntOfPeople-cntOfDwarfs) {
            if (currentSumOfHeight == 100) {
                return heightOfFalseDwarf;
            }
            return null;
        }
        if (idxOfPeople == cntOfPeople) {
            return null;
        }

        currentSumOfHeight -= heightOfPeople[idxOfPeople];
        heightOfFalseDwarf[cntOfCurrentFalseDwarf] = heightOfPeople[idxOfPeople];
        int[] answer = getFalseDwarfsIndex(heightOfPeople, heightOfFalseDwarf, currentSumOfHeight, cntOfCurrentFalseDwarf+1, idxOfPeople+1);
        if (answer != null) {
            return answer;
        }
        currentSumOfHeight += heightOfPeople[idxOfPeople];
        heightOfFalseDwarf[cntOfCurrentFalseDwarf] = 0;
        answer = getFalseDwarfsIndex(heightOfPeople, heightOfFalseDwarf, currentSumOfHeight, cntOfCurrentFalseDwarf, idxOfPeople+1);
        if (answer != null) {
            return answer;
        }

        return null;
    }
}

사실 그냥 이중 for문으로 풀어도 되는 문제지만, 2명이 아닌 3명이 스파이거나 혹은 5명이 스파일 때를 대비해서 코드를 짜줬다.