[JAVA] 백준 비트마스킹 뿌수기1

 

이번에는 비트마스킹을 공부해보려고 한다.

비트 연산을 안배운지 너무 오래돼서 브론즈문제부터 차근차근 풀 예정이다.

 

 

 

개념정리 - XOR 연산자

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

true ^ true = false
false ^ true = true
true ^ false = true
false ^ false = false

• 자바의 XOR연산자는 두 값이 다르면 true를 반환한다.
• 1은 true의 의미를 가지고 있다고 c언어처럼 생각하면 되겠다

 

 

 

개념정리 - 비트 반전 연산

~1 = 0
~0 = 1

• 말그대로 비트를 반전하는 연산

 

 

 

27960 사격 내기 - 브론즈3

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

27960번: 사격 내기

• 64 이상의 점수를 만들기 위해서는 무조건 64가 선택되어야한다
• 1+2+4+8+16+32를 다 더해도 64에 미치지 못한다
• 이진수 비트로 생각하면 더 쉽게 떠올릴 수 있음

 

class Main {
   public static void main(String args[]) throws Exception {
      boolean[] scores1 = new boolean[10];
      boolean[] scores2 = new boolean[10];

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());

      for (int i =9; i>=0; i--) {
          if (a>=Math.pow(2, i)) {
              scores1[i] = true;
              a -= Math.pow(2, i);
          }

          if (b>=Math.pow(2, i)) {
              scores2[i] = true;
              b -= Math.pow(2, i);
          }
      }

      int result = 0;
      for (int i =0; i<10; i++) {
          if (scores1[i]^scores2[i]) {
              result += Math.pow(2, i);
          }
      }

      System.out.println(result);
   }
}

 

 

 

 

12833 XORXORXOR - 브론즈1

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

12833번: XORXORXOR

• 직접 적어보면 쉽게 규칙을 찾을 수 있다
• C가 2의 배수이면 답은 A이고, 2의 배수가 아니면 답은 A^B이다.

 

 

 

public class Solution {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int cnt = Integer.parseInt(st.nextToken());

        if (cnt % 2 == 0) {
            System.out.println(a);
        } else {
            System.out.println(a^b);
        }
    }
}

 

 

 

 

24389 2의 보수 - 브론즈1

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

24389번: 2의 보수

• 규칙을 찾으려고 했는데 좀 복잡해서 그냥 반전시키고 보수를 구했다

 

public class Solution {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int a = Integer.parseInt(br.readLine());
        int b = ~a + 1;

        int c = a^b;
        int result = 0;
        for (char character: Integer.toBinaryString(c).toCharArray()) {
            if (character == '1') {
                result ++;
            }
        }

        System.out.println(result);
    }
}

• 다행히 시간초과는 나지 않았다

 

 

 

 

11723 집합 - 실버5

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

11723번: 집합

• set에 넣고 무지성으로 푸니 시간초과가 났다
  • 연산의 수가 300만 개인게 문제인듯
• 모르겠어서 구글링을 해보고 풀었다
  • 비트마스킹 개념을 모르면 애초에 풀 수 없는 문제인 것 같다.
  • 너무 생소한 개념이라 구글링하길 잘했다는 생각이 든다
• 비트마스킹을 완전히 이해한 풀이
  • add 시 1 << x와 bit OR연산 활용
  • remove 시 1 << x를 ~연산을 사용해 비트를 뒤집고 bit AND 연산 활용
  • check 시 x의 체크 여부를 확인하기 위해 1 << x와 마스킹한 값을 AND연산
  • toggle: 1<<x  XOR연산 사용
  • all: (1 << 21) -1
  • empty: 0으로 변경
  • https://myeongju00.tistory.com/31
    • 참고한 블로그!! 감사합니다

 

개념정리

• Integer의 최댓값은 2의 31승-1 이다.
• x는 20밖에 안되기 때문에 충분히 비트연산을 할 수 있다. (빠른 삽입, 삭제를 위해)
• add: 20만큼 옮겨진 x값을 결과값에 or연산으로 더해준다 
• remove: 2를 삭제해야할 경우 10을 만들고 비트를 뒤집는다 -> 111111101 
  • 이걸 And연산해주면 됨
• check 시 1<<x값으로 마스킹
• toggle시 XOR연산 사용 (있으면 빼고(1 1) 없으면 넣고(0 1))
• all 시 전부 1비트로 바꿈
  • 입력이 최대 20이니까 (1<<21)에서 1을 빼주면 20개의 111을 만들 수 있다
• empty는 전부 0비트로 바꿈

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());
        int result = 0;

        StringBuilder sb = new StringBuilder();
        for (int i =0; i<cnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String method = st.nextToken();

            if (method.equals("all")) {
                result = (1 << 21)-1;
            } else if (method.equals("empty")) {
                result = 0;
            } else {
                int value = Integer.parseInt(st.nextToken());
                if (method.equals("add")) {
                    result = result | (1 << value);
                } else if (method.equals("remove")) {
                    result = result & ~(1 << value);
                } else if (method.equals("check")) {
                    if ((result & (1 << value)) == 0) {
                        sb.append(0 + "\n");
                    } else {
                        sb.append(1 + "\n");
                    }
                } else if (method.equals("toggle")) {
                    result = result ^ (1 << value); //1 1 , 0 1
                }
            }
        }

        System.out.print(sb);
    }
}

• 비트마스킹을 잘 사용한 문제!! 재미있었다

 

 

 

 

1094 막대기 - 실버5

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

1094번: 막대기

1. 64인 막대를 절반으로 자름
2. 32 남음
   1. 32가 원하는 값보다 크면 32로 하고
   2. 32가 원하는 값보다 작으면 32 32 2개로 함
3. 가진 막대 중 작은 거 절반으로 자르기~ 계속 반복

• 구현만 잘하면 될 것 같다

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());

        int total = 64;
        int current = 64;
        int cnt =1;

        while (total != x) {
            if (total - current/2 >= x) {
                total -= current/2;
            } else {
                cnt ++;
            }
            current /=2;
        }

        System.out.print(cnt);
    }
}

• 비트마스킹보단 그냥 구현한 느낌인 것 같아서 다른 풀이를 찾아봤다

 

다른풀이 -> 비트마스킹으로 푼 풀이

• 이 풀이가 더 깔끔하고 비트마스킹에 가까운 것 같다
• https://1-7171771.tistory.com/19
• 같은 크기의 막대가 2개 이상일 수도 있기 때문에 여러번 빼줄 수 있도록 while문을 구성하였음
• 이 방법으로도 한 번 풀어봤다

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());

        int stick = 64;
        int cnt = 0;

        while (x != 0) {
            if (x >= stick) {
                x -= stick;
                cnt++;
            } else {
                stick /= 2;
            }
        }

        System.out.print(cnt);
    }
}

 

 

 

1740 거듭제곱 - 실버4

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

1740번: 거듭제곱

 

• 규칙을 찾아내야 문제를 풀 수 있다.
• 쭉 다 적어보면 3의  k승이 포함되는 경우의 수가 2의 배수로 늘어난다.
• 이를 이용하여 k와 개수를 세고 순서를 찾아내면 된다

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Long inputNum = Long.parseLong(br.readLine());

        Long outputNum = 0L;
        while (inputNum > 0L) {
            Long cnt = 0L;
            Long orderPlus = 1L;
            Long threeGop = 1L;
            while (inputNum >= orderPlus * 2L) {
                orderPlus *= 2L;
                cnt++;
                threeGop *= 3;
            }
            
            inputNum -= orderPlus;
            outputNum += threeGop;
        }
        System.out.println(outputNum);
    }
}

• 규칙을 찾고 구현도 숫자에 맞게 잘 해야한다
• 규칙만 찾는 게 아니라 비트마스킹 방식으로 풀어야한다는 생각을 해야 더 좋은 풀이가 나오는 것 같다
• 나한테는 너무 어려워서 몇 번 더 풀어봐야할 것 같다. 

 

 

 

 

14936 엘리베이터 장난 - 실버4

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

14936번: 엘리베이터 장난

• 비트마스킹이라고 해서 XOR로 반전할 생각을 했는데 생각이상으로 N이 너무 컸다
• 내 나름대로 풀었다가 시간초과가 날 게 뻔해서 정답을 찾아봤다. 한 가지의 풀이만 찾을 수 있었음

 

다른풀이: 각 경우를 생각하고 경우의 수를 직접 늘려주는 방법

• https://velog.io/@greenddoovie/%EB%B0%B1%EC%A4%80-14936%EB%B2%88-%EC%97%98%EB%A6%AC%EB%B2%A0%EC%9D%B4%ED%84%B0-%EC%9E%A5%EB%82%9C
• 한 번 누르고 다시 누르면 초기상태로 돌아온다는 점을 잘 이용하신 풀이다
• 생각하기는 쉽지 않지만 이 방법이 맞는풀이인 것 같다
  
  • 전체누르는 버튼 수 = N
  • 홀수 버튼 수 = 짝수면 N/2, 홀수면 N/2+1
  • 짝수 버튼 수 = N/2
  • 3k+1 버튼 수 = 3으로 나눈 나머지가 1이면 N/3+1 나머지가 1이아니면 N/3
• 모든 버튼을 누를 수 있다면 경우의 수 +1
• N이 1이라면 ~
• N이 2라면 ~ 
• N이 3이상이라면~

 

사실 풀이가 이해가 안돼서 시간을 많이 쏟았다

 

다 그리니 규칙이 보인다

다 누르기, 짝수만 선택, 홀수만 선택한 상황에서 다른 걸 누르는건 별로 의미가 없다

이 7가지 경우의 수에서 같을 수 있는 것만 빼면 되겠다

 

 

풀이

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] caseCnt = new int[4];
        caseCnt[0] = N;//다 누르는 경우
        caseCnt[1] = N/2;//짝수만 누르기
        caseCnt[2] = N/2 + (N%2==0? 0: 1);//홀수만 누르기
        caseCnt[3] = N/3 + (N%3==1? 1: 0);//3k-1누르기

        int result = 1;
        if (N == 1) {
            if (M >= 1) {
                result ++;
            }
        } else if (N == 2) {
            if (M >= 1) {
                result += 2;
                if (M >= 2) {
                    result += 1;
                }
            }
        } else {
            if (M >= caseCnt[1]) {
                result += 1;

                if (M >= caseCnt[0]) {
                    result += 1;
                }

                if (M >= caseCnt[2]) {
                    result += 1;
                }
            }

            if (M >= caseCnt[3]) {
                result += 1;
                M -= caseCnt[3];

                if (M >= caseCnt[1]) {
                    result += 1;

                    if (M >= caseCnt[0]) {
                        result += 1;
                    }

                    if (M >= caseCnt[2]) {
                        result += 1;
                    }
                }
            }
        }

        System.out.println(result);
    }
}

 

 

풀이가 이게 끝이다

• 1인 경우에 M이 1개이상인지 확인하고 경우의 수를 +1
• 2인 경우에 M이 1개 이상이라면 경우의 수 +2
  • M이 2개이상이라면 경우의 수 +1
• 3이상인 경우에는 다 누르는 경우, 짝수인 경우, 홀수인 경우, 3k+1인 경우의 수를 잘 세서 해당 경우의 수를 +1해주면 된다
• 이걸 코드에 녹였다

 

 

 

 

비트마스킹은 실버부터 쉽지않다.. 이게 어떻게 실버인지 궁금한 문제들이 많다

조금 더 뿌수면서 익숙해져야겠다