[BOJ-2309][비트마스킹] 일곱 난쟁이 -Java

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

2309번: 일곱 난쟁이

package algo;

import java.util.Arrays;
import java.util.Scanner;

public class boj_2001_보석줍기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] height = new int[9];
		for (int j = 0; j < 9; j++) {
			height[j] = sc.nextInt();
		}

		int i = 0;
		for (; i < 1 << 9; i++) {
			if (Integer.bitCount(i) == 7) { // 7개 선택

				int sum = 0;
				for (int j = 0; j < 9; j++) {
					if ((i & (1 << j)) > 0)
						sum += height[j];
				}
				if (sum == 100)
					break;
			}
		}

		int[] answer = new int[7];
		int index = 0;
		for (int j = 0; j < height.length; j++) {
			if ((i & (1 << j)) > 0)
				answer[index++] = height[j];
		}

		Arrays.sort(answer);
		for (int j = 0; j < 7; j++) {
			System.out.println(answer[j]);
		}

	}

}

소요시간 : 10분

 

조합 문제인데 비트 마스킹을 이용해서 풀어봤습니다.

 

 

간략하게 비트마스킹에 대해 설명해보자면

 

x << y    ->  x의 각 비트를 y만큼 왼쪽으로 이동

1<<2     ->  1의 각 비트를 2번 왼쪽으로 이동 -> 1 -> 100 이 되어서 결과는 4

 

이를 통해서 visited배열을 만들지 않고 비트 마스킹을 통해 확인할 수 있습니다.

 

23 & (1 << 2)  를 하게 되면

23     : 0 0 0 1 0 1 1 1

1<<2 : 0 0 0 0 0 1 0 0

이므로 4가 나오게 됩니다.

 

만약 위의 연산을 통해 0보다 큰 수가 나온다면 그 자리는 1로 마스킹되어 있다는 말입니다

 

끝