백준/탐색 (9) 썸네일형 리스트형 [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가 되는 경우의 수를 구하.. [COCI] 백준 3020 - 개똥벌레 icpc.me/3020 종유석과 석순을 살펴보면 어떤 식으로 나열되어 있든 부숴야 될 갯수에는 변함이 없다는 것이다. 그 즉슨 종유석과 석순을 정렬하고 이진 탐색을 통해 어떤 높이에서 몇개 부숴야 하는지 확인하면 빠르게 풀 수 있음을 알 수 있다. 1부터 h까지 반복문을 돌려 해당 높이에서 최소한으로 부술 수 있는지, 최소한으로 부술 수 있는 경우가 몇개인지 확인하면 AC를 받을 수 있다. 시간복잡도 $O(HlogN)$ 전체 코드 더보기 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 28 29 30 31 32 33 34 35 36 37 38 #include using namespace std; int n, h; int br.. 이전 1 2 다음
