백준/탐색 (11) 썸네일형 리스트형 [KOI] 백준 2502 - 떡 먹는 호랑이 https://www.acmicpc.net/problem/2502 힌트 더보기 첫날에 준 떡의 양을 $f_{1}$, 둘째 날에 준 떡의 양을 $f_{2}$라고 하자. 떡을 주는 규칙을 살펴보면 $f_{n} = f_{n - 1} + f_{n - 2}$으로 피보나치 수열과 같은 점화식이다. 조건을 만족하는 적절한 $f_{1}$과 $f_{2}$는 $O(DK \log K)$의 시간복잡도로 찾을 수 있다. $f_{1}$가 정해져 있을 때 $f_{2}$를 찾는 방법을 생각한다. 풀이 더보기 선형 점화식 $f_{n} = f_{n - 1} + f_{n - 2}$로 계산한 $f_{d}$가 주어질 때 $f_{1}$과 $f_{2}$를 구하는 문제이다. 각 항에 대해 값을 1부터 $10^{5}$까지 무식하게 찾으면 시간복잡도.. 백준 4160 - 이혼 https://www.acmicpc.net/problem/4160 힌트 더보기 브루트 포스를 시행하면 $3^{24}$만큼 경우의 수가 있다. 밋 인 더 미들을 통해 $O(3^{12})$로 풀 수 있다. 풀이 더보기 다음 3가지를 한 번에 고려해보자. 잭이 가지는 집의 가치 질이 가지는 집의 가치 판매하는 집의 가치 3가지를 각각 따져서 브루트 포스로 잭의 집 가치와 질의 집 가치가 같은 경우를 찾으면 $3^{24}$만큼 경우의 수가 나오고 이는 매우 커서 30초라는 제한 시간 안에 어림도 없음을 알 수 있다. 밋 인 더 미들을 기법을 사용해 주어진 집을 2개의 부분 집합으로 쪼개자. 그러면 각 집합의 크기는 최대 12가 된다. 이때 우리는 다음을 구할 것이다. 분할된 집합을 각각 $s_{1}$, $s_{.. [ICPC] 백준 20047 - 동전 옮기기 https://www.acmicpc.net/problem/20047 힌트 더보기 선택한 동전은 단 두 개다. 완전 탐색을 해도 분기가 많이 발생하지 않는다. 풀이 더보기 동전 두 개의 위치를 바꿔가면서(그들의 상대적인 순서는 유지하고) T와 같은 배치를 만들 수 있는지 묻는 문제다. 배치 S에서 주어진 index에 해당하는 동전을 따로 뺀 뒤 동전을 처음부터 배치한다고 하면 다음 분기로 배치를 결정할 수 있다. 동전 두 개를 제거한 S의 배치 순서를 pos라 하고 T의 순서를 idx라 한다면 1. S[pos]와 T[idx]가 일치하면 그대로 놓기 2. T[idx]와 동전 두 개 중 하나를 조건에 맞게 놓기 이를 DFS로 구현하면 정답을 받을 수 있다. 자세한 구현은 밑에 소스를 참조한다. #pragma .. 백준 2208 - 보석 줍기 www.acmicpc.net/problem/2208 풀이 배열의 prefix sum을 계산해준다. n개의 보석만큼 반복문을 돌리는데 다음 계산의 최댓값이 정답이 된다. 보석 i번째까지 전부 먹었을 때 누적합 - 이전 구간에서 최대로 손해를 입는 누적합 구현에서는 이전 구간에서 최대로 손해를 입는 누적합을 저장하기 위해 별도의 변수를 두었다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include using namespace std; int ar[100001]; int prefix[100001]; int n, m; int res; int main() { cin.tie(0); ios::sync_with.. 백준 1208 - 부분수열의 합 2 www.acmicpc.net/problem/1208 주어진 조건에서 부분수열을 생성하는 경우는 $2^{40}$으로 단순한 완전 탐색으로 풀 수 없다. 주어진 수열을 절반으로 나눈 상황을 가정해보자. 각 부분에서 수열을 생성하는 경우는 완전탐색으로 $2^{20}$이고 두개의 부분을 탐색해야 하므로 $2 \times 2^{20}$가 되어 각 부분의 부분수열을 구한 후 서로 결합하는 방법으로 문제를 해결 할 수 있게 된다. 이처럼 상태 공간을 반으로 나누고 두 상태 공간의 접점을 탐색하는 기법을 meet in the middle이라 부른다. 주어진 수를 서로 다른 배열에 담아 비트마스킹으로 부분수열의 합을 벡터에 저장하고 각 벡터에서 s의 개수 + 각 벡터에 있는 원소를 더했을 때 s가 되는 경우의 수를 구하.. 이전 1 2 3 다음
