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

 

 

비트마스킹 시즌2다.

비트마스킹은 뿌수기 시리즈 중 가장 어렵다고 느껴진다.. 비트마스킹이 내 취약점인 것 같다. 

더 열심히해야지.. 

 

 

17419 비트가 넘쳐흘러 - 실버4

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

17419번: 비트가 넘쳐흘러

• 0이 될 때까지 계속 연산을 반복하면 시간초과가 날 것 같았지만, 규칙이 떠오르지 않아서 그냥 해봤다가 51%에서 안움직였다
• N의 개수가 100만이었기 때문에 long으로도 처리가 안된 것이었다
• 어쩔 수 없이 규칙을 찾으려고 노력했다

 

• 직접 하나하나 적어 규칙을 발견했다
• 원본의 가장 작은 1부터 사라진다
• 1의 개수만 구하면 답이 될 것 같다

 

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

        int result = 0;
        for (char c: input.toCharArray()) {
            if (c == '1') {
                result ++;
            }
        }

        System.out.println(result);
    }
}

 

 

 

 

 

11811 데스스타 - 실버3

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

11811번: 데스스타

• 어떤 수1 & 어떤 수2 = 결과
• 결과를 기반으로 수를 구해내야하는 것 같다
• 주 대각선을 읽을 수 없으므로 i != j 행렬만 읽어서 답을 내야한다

 

• 비트 & 연산의 경우 1 1인 경우만 1이 나오는 점을 이용해서 유추해야한다
• 어떤 부분이 1인지 체크하면서 수열을 확정해야하는 게 좋겠다

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

        int[] result = new int[size];
        for (int i =0; i<size; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j =0; j<size; j++) {
                int value = Integer.parseInt(st.nextToken());
                if (i != j) {
                    result[i] |= value;
                    result[j] |= value;
                }
            }
        }

        for (int num: result) {
            System.out.print(num + " ");
        }
    }
}

• 1이 나오면 해당 비트를 원래 비트에 추가해주는 식으로 구현했다
• 주의점은 이미 1이 있을 때는 해당 1은 그대로 둬야한다는 거다. 그래서 비트 OR 연산자를 이용하여 1을 추가해줬다
• i == j 인 경우는 고려하면 안되므로 아닌 경우만 계산했다

 

 

 

 

16508 전공책 - 실버3

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

16508번: 전공책

• 같은 졸업생인 입장에서 민호는 광기인 것 같다
• 그리디하게 풀면 되지않을까? 싼 가격부터 글자 골라내기 dfs로 가보면 될 것 같다
• 하지만 visited를 어떻게 체크해야할 지 몰라서 구현에 실패했다. 다른 풀이들을 분석하면서 배웠다

 

다른풀이1. 목표 단어의 알파벳개수를 저장한 후, 완전탐색

• 목표하는 알파벳개수를 저장하고, 모든 책을 돌면서 visited를 HashMap, int배열 등에 저장하면서 최솟값을 찾아낸다
• 알파벳의 visited를 잘 저장하는 게 핵심이다

 

<HashMap을 사용한 풀이>

class Book {
    String name;
    int price;

    public Book(String name, int price) {
        this.name = name;
        this.price = price;
    }
}

public class Main {
    static Book[] bookArr;
    static Map<Character, Integer> targetMap = new HashMap<>();
    static Map<Character, Integer> currentMap = new HashMap<>();
    static int minMoney =Integer.MAX_VALUE;

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

        bookArr = new Book[bookCnt];

        for (int i = 0; i< bookCnt; i++) {
            StringTokenizer st =new StringTokenizer(br.readLine());
            int price=  Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            bookArr[i] = new Book(name, price);
        }

        for (char c: targetBookName.toCharArray())
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);

        dfs(0, 0);

        if (minMoney == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(minMoney);
    }

    private static void dfs(int idx, int money) {
        boolean isFinish = true;

        for (char c: targetMap.keySet()) {
            if (currentMap.getOrDefault(c, 0) < targetMap.get(c)) {
                isFinish = false;
                break;
            }
        }

        if (isFinish) {
            if (minMoney > money)
                minMoney = money;

            return;
        }

        if (idx >= bookArr.length) 
            return;

        Book currentBook = bookArr[idx];

        //선택
        for (char c: currentBook.name.toCharArray()) 
            currentMap.put(c, currentMap.getOrDefault(c, 0)+1);

        dfs(idx+1, money + currentBook.price);

        //선택안함
        for (char c: currentBook.name.toCharArray()) 
            currentMap.put(c, currentMap.get(c)-1);

        dfs(idx+1, money);
    }
}

• 선택하는 경우와 선택하지 않는 경우를 구분하여 dfs를 돌린다
• getOrDefault를 잘 사용하는 게 중요하다

 

알파벳을 인덱스로 사용한 배열 풀이

class Book {
    String name;
    int price;

    public Book(String name, int price) {
        this.name = name;
        this.price = price;
    }
}

public class Main {
    static Book[] bookArr;
    static int[] targetCnt = new int[26];
    static int[] currentCnt = new int[26];
    static int minMoney =Integer.MAX_VALUE;
    static String targetBookName;

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

        bookArr = new Book[bookCnt];

        for (int i = 0; i< bookCnt; i++) {
            StringTokenizer st =new StringTokenizer(br.readLine());
            int price=  Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            bookArr[i] = new Book(name, price);
        }

        for (char c: targetBookName.toCharArray())
            targetCnt[c - 'A'] ++;

        dfs(0, 0);

        if (minMoney == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(minMoney);
    }

    private static void dfs(int idx, int money) {
        boolean isFinish = true;

        for (char c: targetBookName.toCharArray()) {
            if (currentCnt[c-'A'] < targetCnt[c - 'A']) {
                isFinish = false;
                break;
            }
        }

        if (isFinish) {
            if (minMoney > money)
                minMoney = money;

            return;
        }

        if (idx >= bookArr.length)
            return;

        Book currentBook = bookArr[idx];

        //선택
        for (char c: currentBook.name.toCharArray())
            currentCnt[c - 'A'] ++;

        dfs(idx+1, money + currentBook.price);

        //선택안함
        for (char c: currentBook.name.toCharArray())
            currentCnt[c - 'A'] --;

        dfs(idx+1, money);
    }
}

• 이 방법이 시간이 훨씬 적게들고 가독성도 좋다
• 현재 적립된 알파벳 개수를 currentCnt 배열에 저장하여 목표값과 비교한다
• 끝나면 값을 갱신하고 return한다

 

 

 

 

2961 도영이가 만든 맛있는 음식 - 실버2

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

2961번: 도영이가 만든 맛있는 음식

• 완전탐색을 해야할 것 같다
• 100억이므로 long을 사용
• 쓴맛의 전체 합 + 현재 쓴맛의 합보다 신맛의 곱이 많아지면 가지치기를 하는 방식을 사용해보려고 한다

 

public class Main {
    static long minSour = 0;
    static long minDiff = 0;
    static Taste[] tasteArr;

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

        tasteArr = new Taste[cnt];

        for (int i =0; i<cnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long sour = Long.parseLong(st.nextToken());
            long bitterness = Long.parseLong(st.nextToken());
            tasteArr[i] = new Taste(bitterness, sour);

            minSour += bitterness;
        }

        minDiff = Math.abs(tasteArr[0].sour - tasteArr[0].bitterness);
        minSour += minDiff;

        for (int i =0; i< tasteArr.length; i++)
            dfs(i+1,tasteArr[i].sour, tasteArr[i].bitterness);

        System.out.println(minDiff);
    }

    private static void dfs(int idx, long sour, long bitterness) {
        long tmp = Math.abs(sour - bitterness);
        if (tmp < minDiff)
            minDiff = tmp;

        if (idx >= tasteArr.length)
            return;

        Taste taste = tasteArr[idx];
        dfs(idx+1, sour * taste.sour, bitterness + taste.bitterness);
        dfs(idx+1, sour, bitterness);
    }
}

• 비트마스킹인데 완전탐색만 쓴 것 같아서 다른 풀이도 확인해봤다

 

class Taste {
    int sour;
    int bitterness;

    public Taste(int sour, int bitterness) {
        this.sour = sour;
        this.bitterness = bitterness;
    }
}

public class Main {
    static int N;
    static int tmpSour;
    static int tmpBitterness;
    static int min = Integer.MAX_VALUE;
    static ArrayList<Taste> list = new ArrayList<>();

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

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int sour = Integer.parseInt(st.nextToken());
            int bitterness = Integer.parseInt(st.nextToken());
            list.add(new Taste(sour, bitterness));
        }

        subset(1 << N);
        System.out.println(min);
    }

    public static void subset(int caseCount) {
        for (int flag = 1; flag < caseCount; flag++) { // 모든 경우의 수 구하기
            tmpSour = 1;
            tmpBitterness = 0;
            for (int j = 0; j < N; j++) {
                if ((flag &    1 << j) != 0) { //재료에서 뽑아오기
                    Taste taste = list.get(j);
                    tmpSour *= taste.sour;
                    tmpBitterness += taste.bitterness;
                }
            }

            if (min > Math.abs(tmpSour - tmpBitterness))
                min = Math.abs(tmpSour - tmpBitterness);
        }
    }
}

• 참고한 풀이: https://verycrazy.tistory.com/142?category=1052323
• 전체 케이스를 101, 111, 001 이런식으로 표현해서 완전탐색을 하는 방법이다
• dfs와 시간은 거의 비슷하게 걸린다
• 이 문제는 굳이 비트마스킹으로 풀지않아도 될 것 같다

 

 

 

 

15787 기차가 어둠을 헤치고 은하수를 - 실버2

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

15787번: 기차가 어둠을 헤치고 은하수를

• 이미 타있다면 아무런 행동도 하지 않고, 아무도 앉아있지 않다면 아무런 행동을 하지 않는다 -> 여기서 비트마스킹 냄새가 난다
• 모두 한 칸씩 땡겨앉고 한 명 버리기 -> 비트마스킹을 쓰면 되겠다

 

public class Main {
	public static void main(String args[]) throws Exception {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 StringTokenizer st = new StringTokenizer(br.readLine());
		 
		 int trainCnt = Integer.parseInt(st.nextToken());
		 int commandCnt = Integer.parseInt(st.nextToken());
		 
		 int[] trains = new int[trainCnt];
		 
		 int max = (int) ((long)(1<<20) - 1);
		 
		 for (int i =0; i<commandCnt; i++) {
			 st = new StringTokenizer(br.readLine());
			 
			 int command = Integer.parseInt(st.nextToken());
			 int train = Integer.parseInt(st.nextToken())-1;
			 if (command == 1) {
				 int sit = Integer.parseInt(st.nextToken())-1;
				 
				 int move = (1 << (sit));
				 trains[train] = trains[train] | move;
			 } else if (command == 2) {
				 int sit = Integer.parseInt(st.nextToken())-1;
				 trains[train] = (~(1 << sit)) & trains[train]; 
			 } else if (command == 3) {
				 trains[train] = trains[train] << 1;
				 trains[train] = trains[train] & max; 
			 } else if (command == 4) {
				 trains[train] = trains[train] >> 1;
			 }
		 }
		 
		 List<Integer> list = new ArrayList<>();
		 
		 for (int currentTrain: trains) {
			 boolean canInput = true;
			 for (int tmp: list) {
				 if ((tmp ^ currentTrain) == 0) {
					 canInput = false;
					 break;
				 }
			 }
			 
			 if(canInput) 
				 list.add(currentTrain);
		 }
		 
		 System.out.println(list.size());
	}
}

• 그냥 하라는 대로 비트마스킹을 하면 된다
  • 하나 추가: (1<<sit) 를 bit OR 연산
  • 하나 빼기: (~(1<<sit)) 를 bit AND 연산
  • 한 칸씩 뒤로가기: <<연산을 하되, 맨 앞자리를 삭제하도록 11111을 & 마스킹
  • 한 칸씩 앞으로가기: >>연산 수행
• 통과할 수 있는 기차를 list에 저장하고, 해당 기차들과 XOR연산으로 겹치는지 확인한다

 

 

 

 

1052 물병 - 실버1

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

1052번: 물병

• 2의 배수로 늘어나는 포인트가 와닿지 않아 풀이를 찾아봤다
• 다양한 방법이 있었고, 크게 3가지 풀이를 찾아봤다

 

 

1. 비트마스킹 이용 -> k개수보다 1의 개수가 작아질 때까지 해당 1자릿값을 더해주는 방식

• 1000 일 경우 1이 1개이지만,  4 2개로 만들 수 있기 때문에 2도 가능하다/ 2 4개로도 만들 수 있어서 4도 가능
• k개수보다 작거나 같을 때까지 이진수 1에 해당하는 숫자를 더해준다
• 아이디어를 떠올리기는 쉽지 않지만, 알면 쉽게 풀 수 있는 문제인 것 같다

public class Main {
	public static void main(String args[]) throws Exception {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 
		 StringTokenizer st = new StringTokenizer(br.readLine());
		 int n = Integer.parseInt(st.nextToken());
		 int k = Integer.parseInt(st.nextToken());
		 
		 int result = 0;
		 while (Integer.bitCount(n) > k) {
			 int tmp = n & (-n);
			 n += tmp;
			 result += tmp;
		 }
		 
		 System.out.println(result);
	}
}

 

 

2. 이진수 1값을 찾고, 원하는 개수를 만들기 위해 빼주는 방법 사용

• 굉장히 신박한 풀이다(머리를 맞은 기분이 들었음 .. 구글링 해서 다른 풀이 찾아보길 잘한 것 같다)
• 위 비트마스킹 풀이와 비슷한듯 다르다
• 위 풀이는 될 때까지 해당 1자리값을 더해주는 방법을 사용하지만, 이 풀이는 이를 한 방에 해결한다
• 아이디어를 떠올리기는 쉽지 않을 것 같지만, 알면 빠르게 풀린다
• 자릿수에 유의하여 풀어야한다
• https://tussle.tistory.com/950

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 K = Integer.parseInt(st.nextToken());
        
        int answer = 0, index = -1;
        String bitN = Integer.toBinaryString(N);	//N ▶ 2진
        int ones = Integer.bitCount(N);	//2진수 1의 개수
        
        if(ones > K){	//1의 개수 > K 일 때
            //K번째 '1'을 기준으로 만들어야 하는 형태의 위치 구하기
            for (int i = 0; i < bitN.length(); i++) {
                if (K == 0) {
                    index = i;
                    break;
                }
                if (bitN.charAt(i) == '1')
                    K--;
            }
            
            String temp = bitN.substring(index);	//바꿔야 하는 값 110
            int t = Integer.parseInt(temp, 2);	//바꿔야 하는 값의 10진수 값 
            /*
            	바꿔야 하는 값이 0이 아닐 때
            	Math.pow(2, bitN.length() - index) : 만들어야 하는 형태의 10진수 값
            	t : 바꿔야 하는 값에 10진수 값
            	Math.pow(2, bitN.length() - index) - t : 물병을 사야하는 개수
            */
            if (t != 0)
                answer = (int) (Math.pow(2, bitN.length() - index) - t); 
        }
        
        System.out.println(answer);
    }
}

 

반복을 하지 않으니 시간이 조금 줄어들었다

 

 

다른풀이3

• 1번 풀이와 비슷한듯 다르다
• 1번 풀이는 가장 뒤에 있는 1을 바로 찾았다면, 얘는 2로 나누면서 찾아나간다
• 위 풀이를 이해했다면 그렇게 어렵지는 않다
• 물론 아이디어를 떠올리긴 쉽지 않았다. 비트마스킹에 익숙해질 필요성이 느껴진다...
• https://ukyonge.tistory.com/210

 

 

 

 

1497 기타콘서트 - 실버1

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

1497번: 기타콘서트

• 50은 long 타입 비트마스킹으로 풀 수 있을 것 같아 비트마스킹하되 완전탐색하도록 풀었다

 

public class Main{
	static long[] guitarInfo;
	static long targetMask = 0;
    
    static int minGuitarCnt = Integer.MAX_VALUE;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int guitarCnt = Integer.parseInt(st.nextToken());

        targetMask = 0;
        
        guitarInfo = new long[guitarCnt];
        
        for (int i =0; i<guitarCnt; i++) {
        	st = new StringTokenizer(br.readLine());
        	st.nextToken();
        	String input = st.nextToken();
        	StringBuilder replace = new StringBuilder();
        	
        	for (int j=0; j<input.length(); j++) {
        		if (input.charAt(j) == 'Y')
        			replace.append(1);
        		else 
        			replace.append(0);
        	}

        	guitarInfo[i] = Long.parseLong(replace.toString(), 2);
        	targetMask = targetMask | guitarInfo[i];
        }
        
        if (targetMask == 0) {
        	System.out.println(-1);
        } else {
        	dfs(0, 0, 0);
        	
        	System.out.println(minGuitarCnt);
        }
    }
    
    private static void dfs(int idx, long currentMask, int cnt) {
    	if (currentMask == targetMask) {
    		if (minGuitarCnt > cnt) {
    			minGuitarCnt = cnt;
    			return;
    		}
    	}
    	
    	if (idx >= guitarInfo.length) {
    		return;
    	}
        
        if (cnt > minGuitarCnt)
            return;
    	
    	dfs(idx+1, currentMask | guitarInfo[idx], cnt+1);
    	dfs(idx+1, currentMask, cnt);
    }
}

• 기타를 선택하는 경우, 선택하지 않는 경우로 나누어 완전탐색 해줬다

 

 

 

 

 

비트마스킹 쉽지않다...

코테 빈출은 아니라서 다른 부수기시리즈를 병행하면서 자주 풀어줘야할 것 같다. 더 노력해야지