백준/탐색 (9) 썸네일형 리스트형 백준 1522 - 문자열 교환 https://www.acmicpc.net/problem/1522 힌트 더보기 특정한 상태를 만들어 보는 방법을 생각해보자. 그리고 원형의 상태가 문제 풀이에 어떤 영향을 미치는지도 생각해보자. 풀이 더보기 우리는 aaaabbbb 꼴과 같은 상태를 만들어 볼 것이다. 그러면 왼편의 b는 오른편의 a와 바꿔야 할 것이다. 물론 원형이라는 조건 하에 abbbbaaa 같은 문자열도 성립됨을 상기하자. 다만 abbbbaaa를 만드는 것과 aaaabbbb는 구현상 모순이다. 우리는 이 모순을 극복하기 위해 원형이라는 점을 이용해 문자열을 쉬프트 할 것이다. 그러면 문제는 다음과 같이 바뀐다. "원본 문자열을 x번 쉬프트 한 상태에서 aaaabbbb... 꼴로 만드는 연산 횟수" 그러면 각 상태에서 투 포인터로 스.. [KOI] 백준 8983 - 사냥꾼 https://www.acmicpc.net/problem/8983 풀이 각 동물과 사대들의 거리를 생각해보자. 사대들과의 거리를 그래프 형태로 그리면 다음과 같은 형태가 나옴을 눈치챌 수 있다. 그래프의 형태는 유니모달 함수이며 우리는 삼분 탐색으로 닿을 수 있는 가장 짧은 사대를 찾을 수 있음을 알 수 있다. 사대의 좌표를 정렬한 후 입력받은 동물 좌표마다 삼분 탐색을 실시하여 피격당할 수 있는 동물의 마릿수를 구하면 된다. 전체 코드 더보기 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 .. [KOI] 백준 2503 - 숫자 야구 https://www.acmicpc.net/problem/2503 체크리스트 서로 다른 숫자 세 개로 구성된 세 자릿수 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번 다른 자리에 위치하면 볼 한 번 풀이 수가 단 3자리에 1부터 9까지 이므로 3자리 숫자를 모두 검색하는 완전 탐색을 생각해볼 수 있다. 이때 "서로 다른 숫자 세 개"라는 조건에 유의하여 같은 숫자가 있으면 건너뛰도록 한다. 어떤 수 조합이 후보에 포함될 수 있으려면 N개의 질의에 대해 스트라이크와 볼 개수가 일치해야 한다. 하나라도 그렇지 않으면 모순이 발생한 것이므로 생각할 수 있는 조합이 될 수 없다. 모든 수 조합에 대해 N개의 질의를 만족하는 횟수를 구하면 정답을 받을 수 있다. 전체 코드 더보기 1 2 3 4 5 6 7.. [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_{.. 이전 1 2 다음
