목록비트마스킹 (6)

1일1알

백준 15787번 기차가 어둠을 헤치고 은하수를 C++

https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 비트를 이용해서 겹치지 않는 좌석의 기차만 카운팅했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long l..
알고리즘 2023. 4. 5. 08:20
백준 11578번 팀원 모집 C++

https://www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net n과 m이 10 이하이기 때문에 팀이 될 수 있는 모든 경우를 구해서 모든 문제를 풀 수 있는 가장 인원이 적은 팀을 구한다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include ..
알고리즘 2023. 3. 30. 13:00
백준 4991번 로봇 청소기 C++

어떤 더러운 칸들을 청소했는지를 비트로 관리하고 방문 표시를 3차원 배열(비트, 행, 열) 로 관리해서 bfs 탐색을 이용해서 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int r, c; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; struct Info { int row; int col; int dirtyBit; int moveCnt; }; vect..
알고리즘 2022. 7. 26. 12:44
백준 10472번 십자뒤집기 C++

비트마스킹을 활용해서 bfs로 탐색하면서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int dRow[5] = { 0,-1,0,1,0 }; int dCol[5] = { 0,0,1,0,-1 }; int visited[600] = { false }; int arr[3][3] = { {0,1,2},{3,4,5},{6,7,8} }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL)..
알고리즘 2022. 3. 5. 10:55
백준 2082번 시계 C++

0부터 비교하면서 켜지지 않아야 할 곳에 불이 켜져있으면 넘어가고 모두 꺼져있다면 그 번호로 만들 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; vector nums(10, vector(15, true)); vector v(4, vector(15, true)); void Init() { nums[0][4] = false; nums[0][7] = false; nums[0][10] = false; nums[1][0] = false; nums[1]..
알고리즘 2022. 2. 11. 14:53
백준 1052번 물병 C++

우선 n1일 동안 n에서 n을 넘지 않는 최대의 2의 제곱을 빼가면서 n을 줄였다. 물론 k도 1씩 줄여줬다. 빼는 도중에 혹은 while문을 빠져나왔을 때 n이 0이라면 물병을 더 구매할 필요가 없기 때문에 0을 출력하고 프로그램을 종료하였다. n가 0이 아닌 경우에는 n보다 큰 2의 제곱 중 가작 작은 수에서 n을 빼면 구매해야하는 물병의 최솟값이다. 출력 조건에 정답이 없을 경우에는 -1을 출력하라고 했는데, 정답이 없을 경우는 없을 것 같아서 만들지 않았는데 통과되었다. 속임수였던 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include..
알고리즘 2021. 12. 25. 10:59
이전 Prev 1 Next 다음