[백준] 2309번 일곱 난쟁이

생각

Github - https://github.com/hellojdh/Code/tree/master/src/baekjoon/q2000

9명의 난쟁이의 키가 주어진다. 7곱 난쟁이의 키의 크기의 합은 100이다.
이 때, 7곱 난쟁이가 될 수 있는 난쟁이들의 키를 오름차순으로 출력하여라.

처음 생각

이렇게 여러개의 조건에서 서로 다른 n개를 택하는 조합의 경우 풀이 방법은 3가지가 있다.
1) 반복문을 통한 완전 탐색
2) 재귀를 통한 완전 탐색
3) 비트 마스크를 통한 완전 탐색

다음 생각

반복문을 통한 완전 탐색에 대해 알아보면, n개를 택하면 되므로 n개의 반복문이 필요하다 따라서 이문제와 같이 7개를 택해야하는 경우에는 적절하지 않다고 볼 수 있다.

▶ 실제로 4개 정도까지는 for문으로 구현을 하는게 더 빠르고, 직관적으로 볼 수 있다. 하지만 7중 반복문이라면 이야기가 달라질 것이다.

다다음 생각

따라서 재귀를 통한 방법과 비트 마스크를 이용한 방법 둘 다 풀어보기로 하였다. 우선 재귀를 이용해서 DFS 탐색을 해나갈 때는 현재 index를 포함 할 것인가? 하지 않을 것인가? 만 따져주면 되기 때문에 이해가 된다면 3개의 방법중 가장 이해하기가 좋은 코드라고 생각한다.

▶ 하지만 사람은 빠른 코드를 추구하고, 메소드를 옮겨다니는 재귀보다는 Bit 단위로 따져주는 비트 마스크가 좀 더 빠르다.

다다다음 생각

비트 마스크는 이 글([Java] 비트 마스크에 대해서 알아보자)에서 설명을 적어 놓았다. C나 C++의 경우는 true 값을 양수 값으로 컨트롤 할 수 있지만 Java는 안되므로 0보다 큰 수로 판단 할 수 있었다.

방안

1) 재귀를 이용한 풀이

package baekjoon.q2000;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class Q2309 {
    static int[] arr,visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        arr = new int[9];
        visited = new int[9];
        for(int i=0;i<9;i++)
            arr[i] = sc.nextInt();
        solve(0,0,0);
    }
    
    // 키의 합은 100, 하나만 출력하면 되므로 출력후 flag로 빠저나온다.
    static boolean flag = false;
    private static void solve(int idx,int cnt,int sum) {
        if(flag) return;
        // 7개를 모았을 때
        if(cnt==7) {
            // 합이 100이라면 
            if(sum==100) {
                int[] result = new int[7];
                // 7개 체크된 값을 받아. 출력한다.
                for(int i=0,index=0;i<9;i++)
                    if(visited[i]==1) result[index++]=arr[i];
                Arrays.sort(result);
                for(int i:result)
                    System.out.println(i);
                flag = true;
            }
            return;
        }
        if(idx>=9) return;
        // 현재 포함
        visited[idx] = 1;
        solve(idx+1,cnt+1,sum+arr[idx]);
        visited[idx] = 0;
        
        // 현재 미포함
        solve(idx+1,cnt,sum);
    }
}
 

2) 비트 마스크를 이용한 풀이

package baekjoon.q2000;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class Q2309_Bit {
    static int[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        arr = new int[9];
        for(int i=0;i<9;i++)
            arr[i] = sc.nextInt();
        // 오름차순 출력을 위해 미리 정렬해두기
        Arrays.sort(arr);
        
        for(int i=0;i<(1<<9);i++) {
            int sum = 0;
            // bit(1) 개수가 7개일 경우
            if(Integer.bitCount(i)==7) {
                for(int j=0;j<9;j++) {
                    //j만큼 1을 이동하여 i와 and 연산 결과가 1이라면(0보다 크다면)
                    if((1<<j&i)>0) sum+=arr[j];
                }
                if(sum==100) {
                    for(int j=0;j<9;j++) 
                        if((1<<j&i)>0) System.out.println(arr[j]);
                    break;
                }
            }
        }
    }
}