본문 바로가기

비트마스킹

[BOJ] 백준 [15787] 기차가 어둠을 헤치고 은하수를 JAVA
알고리즘,PS/백준 2022. 5. 19. [BOJ] 백준 [15787] 기차가 어둠을 헤치고 은하수를 JAVA https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 📝문제 📝풀이 주어진 수의 범위가 커서 비트 마스킹으로 풀어야 하는 문제이다. 0000...00000 으로 총 21개의 0으로 기차의 상태를 체크한다. ( 해당 위치에 1번에 not 을 적용시킨 결과와 and 연산 적용 case 3 => >> 연산으로 한칸 밀어내고 not 연산을 적용시킨 ( 11111110) 과 and 연산 나올 수 있는 모든 경우를 카운트한다. 참고) 비트마스크 연..
[BOJ] 백준 [1052] 물병JAVA
알고리즘,PS/백준 2022. 5. 18. [BOJ] 백준 [1052] 물병JAVA https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 📝문제 풀이 경우의 수 를 하나씩 따져보면 -1 을 출력할 일은 없다. 우선 물통을 안사고 최대한 합친다고 해보자 주어진 n 이 다음과 같을 때 하나씩 보자. case 1 : 0 case 2 : 1 case 3 : 2 1 case 4 : 4 case 5 : 4 1 case 6 : 4 2 ... 남는 물병이 점점 늘어난다. => 병이 모자랄 일은 x 그리고 2^n 의 갯수이면 물병을 사지 않아도 된다. ..
[BOJ] 백준 [1194] 달이 차오른다, 가자. JAVA
알고리즘,PS/백준 2021. 8. 30. [BOJ] 백준 [1194] 달이 차오른다, 가자. JAVA https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제 풀이 아 .. 비트마스킹이란걸 몰라서 한참을 헤매었다.. 결론적으로는 열쇠의 유무를 2^6 = 64 , 즉 visit배열을 3차원으로 열쇠유무까지 추가하면 => visit[높이][너비][열쇠] visit[h][w][64] 이렇게 두고 풀어야 한다는 것이다. 열쇠면 | 연산으로 추가 , 문 이면 & 연산으로 확인하는 식으로해서 탐색을 하면 된다. 1 2 3 4 5..
LIST
Recent Posts
Popular Posts
Archives
Visits
Today
Yesterday

티스토리툴바