비트마스킹

https://www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net 사용한 알고리즘 : 비트마스킹, 백트래킹 ※ 풀이 전략 1. 학생 개인이 풀 수 있는 문제를 2진수로 나타낸다. 풀 수 있는 문제는 1, 풀 수 없는 문제는 0으로 표기한다. ex) 예로 1번 학생이 총 5문제 중 2, 3, 5 번을 풀 수 있다고 한다면 10110 (2) = 22 이다.(오른쪽부터 1번 문제이고, 맨 왼쪽 비트가 5번 문제를 나타낸다.) 2. 백트래킹을 기법을 이용..

https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 사용한 알고리즘 : 비트마스킹 풀이 전략 : 입력한 숫자를 2진수로 생각하고, 해당 2진수 안에 있는 1의 개수가 K개 이하가 될 때까지 1씩 더한다. (비트 1의 개수가 곧 물병의 개수를 의미하기 때문이다.) ex ) 000000001 = 1L 물병 1개 => 총 물병의 개수 : 1 000000010 = 2L 물병 1개 => 총 물병의 개수 : 1 000001010 = 8L 물병 1개, 2L 물병 1..

https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 사용한 알고리즘 : 비트마스킹 풀이 전략 : 기본값을 2^20으로 두고 비트마스크를 통해 승객을 태우거나 하차시킨다. default=Math.pow(2,20) 최초 기차의 상태는 00000 00000 00000 00000 이다. 여기서 비트 마스킹에 사용할 값인 default를 1 00000 00000 00000 00000 로 두고 아래 명령에 따라 변화하는 기차 상태값을 살펴보자. ..

https://www.acmicpc.net/problem/17419 17419번: 비트가 넘쳐흘러 🎶 DJ욱제는 비트에 몸을 맡기는 중이다. 🎶 DJ욱제는 비트에 심취한 나머지, 비트를 비틀어 제껴버리는 문제를 내 버렸다! N자리 이진수 K가 주어진다. K가 0이 아닐 때까지 아래의 연산을 적용 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String args[]) throws IOException{ BufferedRe..