본문 바로가기

비트마스킹7

[백준 13701] 중복 제거 [Java] 풀이 입력받은 N개의 수들에 대해 중복없이 입력 받은대로 수들을 출력해주어야 한다. 이미 입력받은 수인지 확인하는 과정을 단순히 반복문을 돌며 확인한다면 시간초과가 발생한다. 때문에 O(1)만에 이미 입력받은 수 인지 아닌지 여부를 판단해주어야 한다. 입력될 수 있는 수의 범위(2^25 - 1)만큼 배열을 선언해주어 입력 여부를 0과 1로 표현한다면 빠른 시간안에 이미 입력받은 수인지 아닌지 판별이 가능하다. 단, int형 배열을 선언한다면, 메모리 제한에 걸릴 것 이다. 때문에 BitSet을 이용해 수의 범위만큼 배열을 선언해주면서 메모리 제한을 넘지않도록 하자. 입력을 받으며 이미 입력받은 수인지 확인하고, 아니라면 입력받은수로 표시를 하고 결과 버퍼에 저장해주자 java 15는 메모리 제한 예외 대.. 2023. 6. 27.
[백준 14927] 전구 끄기 [C] 풀이 "백준 14939, 불 끄기"와 비슷하지만 행렬의 크기가 다른 문제다. 소스코드 #include #define min(a, b) a = 0 && ny >= 0 && nx < N && ny < N) temp[nx][ny] = (temp[nx][ny] == '1' ? '0' : '1'); } } int main(){ scanf("%d", &N); for (.. 2021. 9. 2.
[백준 14939] 불 끄기 [C] 풀이 주어진 예제는 직관적으로 풀이가 가능하지만 주어질 Test Case들을 고려하면 순차적으로 탐색하면서 풀이해야 한다. 우선 첫 번째 행에서 시도해볼 수 있는 모든 경우의 수를 시도한다면, 2~N번째 행에서는 이전 행의 불을 끄면 된다. N번째 행을 검사해서 불이 전부 다 꺼졌다면 입력된 예제가 모두 불이 꺼진 경우이므로 그때 누른 스위치의 개수들의 최솟값을 저장해 출력해주면 된다. 소스코드 #include #include #include #define min(a, b) a < b ? a : b char bulb[10][10], temp[10][10]; const char* lRow = "##########"; int dx[5] = {0, -1, 1}, dy[5] = {0, 0, 0, -1, 1}; .. 2021. 9. 2.
[백준 9527] 1의 개수 세기 [C] 풀이 16까지 1의 분포는 다음과 같다. N N의 2진수 1의 개수 1 1 1 2 1 0 2 3 1 1 4 4 1 0 0 5 5 1 0 1 7 6 1 1 0 9 7 1 1 1 12 8 1 0 0 0 13 9 1 0 0 1 15 10 1 0 1 0 17 11 1 0 1 1 20 12 1 1 0 0 22 13 1 1 0 1 25 14 1 1 1 0 28 15 1 1 1 1 32 16 1 0 0 0 0 33 2^x 자리 수는 2^(x+1)마다 반복된다는 것을 알 수 있다. 때문에, (N+1)을 2^(x+1)로 나눈 몫을 2^x만큼 곱하면 완전히 반복되는 구간에 존재하는 1의 개수를 구할 수 있다. 완전히 반복되지 않은 구간에서의 1의 개수는, 2^x 자리 수가 1인경우 (N+1)을 2^x로 나눈 나머지의 개수.. 2021. 8. 25.
[백준 2234] 성곽 [C] 풀이 1과, 2의 답은 방 마다 bfs를 사용해 탐색하면 쉽게 구할 수 있다. 3의 답은 방의 각 칸에서 모든 방향으로 벽을 부셔보고 bfs를 사용해 탐색하면 되는데, 매번 방문한 장소를 초기화해주고, 벽을 뚫었다가 탐색이 끝나면 다시 막아주어야 한다. 방향의 순서는 문제에 주어진대로 bit값의 shift연산과 관련이 있으므로 서, 북, 동, 남 순서대로 탐색했다. 소스코드 #include #include #include #define MAX 50 int n, m, graph[MAX][MAX], rear; bool visited[MAX][MAX]; typedef struct{ int x, y; }Point; Point queue[MAX*MAX], d[4] = {{0,-1}, {-1,0}, {0,1}, {.. 2021. 8. 14.
[백준 1094] 막대기 [C] 풀이 X를 비트로 표현했을 때 1의 개수가 필요한 막대의 개수와 일치한다. 소스코드 #include int main(){ int X, cnt = 0; scanf("%d", &X); do{ if (X & 1) cnt++; } while (X >>= 1); printf("%d", cnt); } 출처 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 2021. 8. 14.

티스토리툴바