목록백트래킹 (50)

1일1알

백준 17471번 게리맨더링 C++

1. 한 구역에서 구역으로 갈 수 있는지 확인할 수 있는 2차원 배열을 만든다. 2. 백트래킹으로 구역을 나누는 경우를 모두 찾는다. 3. 두개의 선거구가 있을텐데, 선거구의 구역들이 다 이어져있는지 확인한다. 4. 구역들이 이어져있지만 다른 선거구가 끼어있는 경우를 걸러준다. 5. 두 선거구의 인구 차를 구하면서 최솟값을 찾는다. 골드4문제인데 골드4보단 어려웠던 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define OUT using namespace std; using int..
알고리즘 2022. 8. 20. 11:40
백준 1062번 가르침 C++

백트래킹으로 k개의 글자를 가르치는 경우를 전부 확인해보면 시간초과가 난다. 남극언어는 anta로 시작하고 tica로 끝난다고 했기 때문에 a,c,i,n,t는 무조건 배워야 한다. 그래서 저 글자들은 처음에 배웠다고 가정하고 시작한다. 그러면 글자를 가르치는 경우가 26Ck 에서 21Ck로 줄어서 통과된다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, k; vector strs; vector v(26)..
알고리즘 2022. 8. 17. 12:00
백준 17142번 연구소 3 C++

활성화되는 바이러스의 모든 경우에 대하여 bfs를 해서 가장 작은 시간을 찾았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; const int MAX = 987654321; int n, m; int targetCnt; int ans = MAX; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; struct Info { int row; int col; int mov..
알고리즘 2022. 8. 2. 17:20
Judge - 1233 : 한기대 최고의 보안 시스템 C++

아무것도 없는 상태에서 시작해서 1이 있는 비트의 수가 짝수개라면 뒤에 0을 추가하고, 1이 있는 비트의 수가 홀수개라면 뒤에 1을 추가하는 식으로 해서 백트래킹을 이용해서 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int k; void BT(int num, int cntOf1, int size) { if (size >= k) { cout
알고리즘 2022. 7. 17. 13:20
Judge - 1235 : Please In My Frontyard! C++

스도쿠 문제와 거의 똑같다. 백트래킹을 이용해서 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; const int SIZE = 9; char PIMFYs[SIZE] = { 'A','B', 'C', 'D', 'E', 'F', 'G', 'H', 'I' }; int GetBoxNum(int row, int col) { if (row >= 0 && row = 0 && col = 3 && col = 3 && row =..
알고리즘 2022. 7. 15. 13:32
백준 1189번 컴백홈 C++

백트래킹을 이용하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int r, c, k; int ans = 0; pair start, target; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; vector board(5, vector(5)); vector visited(5, vector(5, false)); void BT(int dist, pair curr) { if (dist ..
알고리즘 2022. 5. 28. 14:15
이전 Prev 1 2 3 4 5 6 7 ··· 9 Next 다음