부분집합 | 비트마스킹

부분집합

1. 반복문
2. 재귀함수
3. 비트마스킹

---

예제문제) SWEA 5215. 햄버거 다이어트

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= T; t++) {
 
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
 
            int[] scores = new int[n];
            int[] cal = new int[n];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                scores[i] = Integer.parseInt(st.nextToken());
                cal[i] = Integer.parseInt(st.nextToken());
            }
             
            int sumCal =0;
            int sumSco =0;
            int max = 0;
            // (1 << n) 부분집합의 개수 = 모든 경우의 수를 검사하겠다
            for (int i = 0; i < (1 << n); i++) {
                sumCal =0;
                sumSco =0;
                // 근데 어떤 원소를 가지고 있는 부분집합이야?
                for (int j = 0; j < n; j++) {
                    if ((i & (1 << j)) > 0) {
                        // 해당 i 는 검사하고 싶은 경우의 부분집합
                        // 뒤에서부터 하나씩 검사, 비교해서 0보다 크면 해당 j번째 원소 선택
                        sumCal += cal[j];
                        sumSco += scores[j];
                    }
                }
                 
                if(sumCal<=l && sumSco > max) {
                    max = sumSco;
                }
            }
 
            System.out.println("#"+t+" "+max);
        }
 
    } //main
 
}

---

비트연산자

1. & : 비트 단위로 AND 연산을 한다.

   둘 다 1이면, 1

2. << : 피연산자의 비트 열을 왼쪽으로 이동시킨다.

   A<<B : A라는 비트를 B번 왼쪽으로 이동
   A>>B : A라는 비트를 B번 오른쪽으로 이동

3. |
   -비트 단위로 OR 연산을 한다.
   -하나라도 1이면, 1
4. ^
   -비트단위로 XOR 연산을 한다.
   -서로 같으면 0, 다르면 1