최근 푼 재밌는 문제들

BOJ 26268

문제 링크

 \(DP_{N}\)을 '\(N\)번째 은행을 반드시 털었을 때, 최대로 벌 수 있는 돈'으로 정의하자. \(i\)번째 은행을 털고, 그 다음에 \(j\)번째 은행을 털기 위해서는 \(X_j - X_i \leq T_j - T_i\)여야 한다. 이걸 그냥 다 찾아보면 \(O(N^2)\)가 되므로, 부등식을 건드리자. \(X_i - T_i\)보다 작거나 같은 \(X_j - T_j\)를 가지는 \(j\)에 대해서만 확인해주면 된다. 세그를 섞어주자.

 

BOJ 8149

문제 링크

 이분 탐색을 걸어주면, 결정 문제로 바뀌게 된다. 가장 가벼운 \(mid\)개의 추를 뽑아주자. 여기에서, 공간이 가장 많이 남은 컨테이너에 가장 무거운 추를 넣어주는 것이 이득이므로, 우선순위 큐를 이용해 열심히 구현하면 된다.

 

BOJ 10007

문제 링크

 2차원에서 다루는 것보다는 1차원이 편하다. 원점에서만 레이저를 발사해야 하기 때문에, 원점 기준으로 선분의 양 끝점을 정렬하고 \([L_i, R_i]\)처럼 구간으로 바꿔주자.

 \(DP_{N, K}\)를 '\(N\)번째 점까지 봤을 때 \(K\)번 레이저를 발사했고, 이때 최대로 맞춘 선분의 개수'로 정의하자. 한 번 맞춘 선분을 다시 맞출 수 없으므로, 지금 레이저를 발사할 때 이전에 발사한 위치가 어디여야 하는지를 전처리해두자. 그리고, 어떤 점에서 레이저를 발사할 때 몇 개의 구간을 맞추게 되는지도 전처리해두자. 그러면 \(O(NK)\)에 풀린다.

 

 조건을 \(K\leq N\)으로 바꿔버리면, Alien Trick을 사용하는 유명한 문제가 된다.

 

BOJ 21305

문제 링크

 \(1\times1\) 크기의 초콜릿만 뽑을 수 있다면, 초콜릿의 개수의 기우성이 답을 결정한다. \(2\times2\)를 제외한 나머지 \(p\times p\) 크기의 초콜릿을 뽑으면, 기우성이 바뀌게 된다. \(2\times2\)가 중요하다는 건데, 초콜릿의 개수가 짝수인 경우는 \(2\times2\) 크기의 초콜릿이 하나라도 존재하면 선공이 이긴다. 아니라면 후공이 이긴다.

 홀수인 경우는, \(p\times p\) 초콜릿을 뽑은 후에 \(2\times2\) 초콜릿이 하나라도 존재한다면 후공이 이긴다. 게임판에 존재하는 가장 큰 \(p\times p\) 초콜릿을 찾자. 이 크기의 초콜릿을 없애는 것으로, \(2\times2\) 초콜릿이 존재하지 않도록 만들 수 있는지를 찾으면 된다. 이를 위해서는 누적합 배열을 만들면 된다. \(pf_{i, j}\) = '\(1, 1\)부터 \(i, j\)까지 존재하는 \(2\times2\) 초콜릿의 개수'로 정의하고, 내가 뽑는 초콜릿에 해당하는 누적합 값이 \(pf_{N, N}\)과 동일한 지를 확인하면 된다.

 

BOJ 6181

문제 링크

 좌표를 \((x+y, x-y)\)로 바꿔주면 편해지는데, 이렇게 하면 두 점 사이의 택시 거리는 \(x\)좌표의 차와 \(y\)좌표의 차 중 최댓값이다. 가장 가까운 두 점을 푸는 것 처럼 풀면 된다. 분할 정복 풀이는 정답 코드를 보고 풀었는데, 스위핑으로 푸는 게 훨씬 쉬운 것 같다..