본문 바로가기
반응형

브루트포스25

백준 2210번 숫자판 점프 - C++ 풀이 1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다. 1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다. 5번 이동하므로 총 탐색해야 하는 상태 수는 25 * (4^5)로 매우 적기 때문에 브루트 포스로 해결할 수 있다. DFS를 통해 모든 경우를 구해서, 만들 수 있는 모든 수를 구해준다. #include #include using namespace std; int board[5][5]; unordered_set st; int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; void DFS(int n, int r, int c, int curr) { if (n == 6) { st.insert(curr); return; } fo.. 2022. 9. 6.
백준 2632번 피자판매 - C++ 풀이 1. B피자에서 연속된 조각을 선택하는 모든 경우를 구해 각 연속합을 만들 수 있는 경우의 수를 구해둔다. 2. A피자에서 연속된 조각을 선택하는 모든 경우에 대해 목표합을 만들기 위한 경우의 수를 더한다. 1. B피자에서 연속된 조각을 선택하는 모든 경우를 구해 각 연속합을 만들 수 있는 경우의 수를 구해둔다. 두 피자에서 연속된 조각을 선택하는 모든 경우를 고려하면 O(N^4)의 시간 복잡도가 소요된다. 따라서 두 피자를 각각 탐색한 뒤, A피자를 기준으로 대응하는 B 피자의 경우의 수를 구하는 방법을 사용하여 O(N^2)에 해결할 것이다. mp[i] = (B 피자에서 연속합이 i가 되도록 조각을 고르는 경우의 수)라고 하자. B 피자에서 연속된 조각을 선택하는 모든 경우에 대해 그 합을 구해 mp .. 2022. 9. 2.
백준 3020번 개똥벌레 - C++ 풀이 1. 종유석과 석순을 따로 저장한다. 2. 이분 탐색을 이용해서 높이 h로 날 때 파괴해야 하는 종유석과 석순의 개수를 구한다. 3. 모든 구간에 대해 파괴해야 하는 장애물의 개수를 구한 뒤 최솟값을 찾는다. 1. 종유석과 석순을 따로 저장한다. 두 장애물의 방향이 다르므로 종유석과 석순을 따로 저장한다. 2. 이분 탐색을 이용해서 높이 h로 날 때 파괴해야 하는 종유석과 석순의 개수를 구한다. 종유석은 끝부분이 h 미만인 것들을 파괴해야 하고, 석순은 끝부분이 h 초과인 것들을 파괴해야 한다. 따라서 종유석과 석순을 각각 정렬한 뒤, 이분 탐색을 이용하여 파괴해야 하는 개수를 각각 구해주면 된다. 3. 모든 구간에 대해 파괴해야 하는 장애물의 개수를 구한 뒤 최솟값을 찾는다. 총 H개의 구간에 대해 파.. 2022. 8. 27.
백준 14391번 종이 조각 - C++ 풀이 1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다. 2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다. 1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다. 모든 칸에 대해 각 칸을 세로 조각으로 사용할지, 가로 조각으로 사용할지 결정한다. 결정 결과를 비트 마스킹으로 나타낼 수 있다. (ex. 가로는 1 세로는 0) 모두 결정한 뒤에는 전체 조각의 합을 구하면 된다. 전체 조각의 합을 구할 때, 인접한 두 칸 A, B가 똑같이 가로 또는 세로 칸일 경우, A와 B는 서로 이어져 있는 긴 조각으로 처리해주어야 한다. 2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다. 모든 경우를 고려한 뒤 그 중 합이 가장 큰 경우를.. 2022. 8. 23.
백준 1285번 동전 뒤집기 - C++ 풀이 1. 각 행을 뒤집을지 여부를 고정한다. 2. 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 그리디 하게 정한다. 1. 각 행을 뒤집을지 여부를 고정한다. 행이 최대 20개, 열이 최대 20개이므로 각 행과 열에 대해 뒤집을지 말지 여부를 결정하는 경우의 수는 2^40가지이다. 따라서 브루트 포스로는 시간 내에 해결할 수 없다. 먼저 행에 대해서만 뒤집을지 여부를 결정해주자. 경우의 수는 2^20가지로 줄어든다. 2. 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 그리디하게 정한다. 행을 뒤집을지 말지 여부를 결정하고 나면, 이제 각 열의 뒤집을지 말지 여부는 그리디 하게 정할 수 있게 된다. 각 열끼리는 서로 영향을 미치지 않으므로, 각 열에 대해 뒤집는 경우와 뒤집지 않는.. 2022. 6. 28.
반응형

티스토리툴바