[BJ] 2309 - 일곱 난쟁이

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

이번 포스트에서는 백준 2309번 문제인, 일곱 난쟁이에 대해 알아보겠습니다.

 

 

접근 방법

사실 문제를 처음 보고 풀 때는, DFS를 생각했습니다. 순서에 상관 없이 합이 100이 되도록 난쟁이의 키들을 고르기만 하면 되니까요. (다 풀고 더 좋은 코드를 찾다보니 이게 바로 조합이라는 것을 알게 되었습니다.)

 

이 문제에서 중요하다고 생각하는 키 포인트는 다음과 같습니다.

• 순서 상관 없음
• 합이 100이 되어야 함
• 난쟁이의 숫자는 7명

순서가 상관 없다는 것에서 부터 순열이 아닌 조합임을 알 수 있고, 트리에서 여러가지 탐색 경로가 같은 경우로 취급된다는 것을 의미합니다. 

합이 100이 되는 것은 재귀 함수의 중단 조건중 하나가 될 수 있다는 것을 의미합니다.

마지막으로 난쟁이의 숫자는 7명이란 조건이 의외로 중요합니다. 트리로 표현하자면 깊이가 7인 경우에만 정답인 케이스가 발생하며, 깊이가 7 이상인 경우에는 탐색을 안해도 되므로, Depth limited Search라고 할 수 있습니다. 사실 해당 문제에선 인풋이 많아봤자 9명이므로, 큰 의미는 없지만요.

 

 

조합

저는 조합을 모르고 구현했지만, 어찌됬건 조합을 사용한 문제이니 조합에 대해서도 짚고 넘어갑시다.

서로 다른 n개 중에서 r개(n≥r) 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합이라고 한다.

조합은 서로 다른 데이터 중에서 n개를 뽑는 것을 의미합니다. 여기서 뽑는 순서가 중요하지 않으면 조합이고, 중요하면 순열이 됩니다. 난쟁이의 키를 선택하는 순서는 중요하지 않으므로 이번 문제는 조합이라고 할 수 있습니다.

 

조합은 재귀함수 및 백트래킹(back tracking)로 구현할 수 있습니다. 이미 선택한 요소들을 판별하기 위해, visited 혹은 selected같은 자료가 추가로 필요합니다. (혹은 인덱스를 공유하는 방법으로 판별할 수 도 있습니다.)

// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
static void combination(int[] arr, boolean[] visited, int start, int end, int remain) {
    if(remain == 0) {
        // 조합 완료!
        return;
    } else {
        for(int i=start; i<end; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, end, remain - 1);
            visited[i] = false;
        }
    }
}

위 코드는 자바로 구현한 백트래킹을 이용한 조합 코드입니다.

arr는 주어진 데이터이며, visited는 선택한 요소들을 판별하기 위한 추가 데이터이며, start는 조합을 시작할 인덱스, end는 조합을 끝낼 인덱스, remain은 선택해야 할 요소의 개수입니다.

 

 

풀이 코드 (java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;

public class Main {
    private static ArrayList<Integer> input = new ArrayList<>();
    private static ArrayList<Integer> answer = new ArrayList<>();

    private static boolean dfs(int tall, int sum, int index, int remain) {
        if (tall + sum > 100) return false;
        answer.add(tall);
        if (tall + sum == 100 && remain == 0) return true;

        for (int i = index + 1; i < 9; i++) {
            if (dfs(input.get(i), tall + sum, i, remain - 1)) return true;
            answer.remove(input.get(i));
        }
        return false;
    }
    
    public static void main(String[] args) {
	// write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (input.size() < 9) {
            try {
                input.add(Integer.parseInt(br.readLine(), 10));
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        int sum = 0;
        int remain = 7;
        for (int i = 0; i < input.size(); i++) {
            if (dfs(input.get(i), sum, i, remain - 1)) break;
            answer.remove(input.get(i));
        }

        answer.sort(Comparator.comparingInt(a -> a));
        answer.forEach(System.out::println);
    }
}

저는 visited라는 추가 데이터를 사용하지 않아서, 조합의 정석적인 코드와는 조금 다릅니다.

remain또한 합이 100이 되는 경우에 한해서만 체크를 합니다. (정석대로라면 최상단에서 체크를 해줘야겟죠.)

이제와서 보니, 불필요하게 삽입 제거 연산을 하는 대신에, visited를 이용하는게 훨씬 나을 것 같습니다.