농 위키

PS 일지 (8)

마지막 수정 시각: 2023-05-07 11:16:22

Prompt412 Round 193

또 8개 다 풀었다. 3연속 올솔브 성공해서 좋다. 이번에도 실버~골드 라인이 좀 전형적인 문제 위주여서 시간을 번 덕분도 있지만, 플래티넘 이상 난이도의 문제들도 풀이를 떠올리는 시간이 좀 단축되긴 한 것 같아서 좋다.

B. BOJ 14557

최소 횟수는 \(\frac{R \cdot C}{2}\) 이다. 그냥 모든 짝을 한 번에 맞추는 경우. 최대 횟수가 어려운데, 대충 생각했을 때 뒤집는 모든 경우가 쌍이 안 맞으면 \(\frac{R \cdot C}{2}\) 번으로 모든 칸을 확인할 수 있고, 여기서 다시 짝을 맞추면 \(\frac{R \cdot C}\) 번의 연산이 필요하다. 그런데 쌍이 안맞는걸 찾는 과정을 반복하면서 마지막 2칸만 남겨놓은 경우 그 중 한칸은 고르고 바로 기존에 골랐던 걸 이용해서 걔랑 짝이 되는 후보를 찾을 수 있다. 이걸로 한 번의 연산을 아낄 수 있고, 따라서 \(R \cdot C - 1\) 번이 최악의 경우가 된다. 증명을 좀 더 엄밀하게 해야할 것 같은데 더 엄밀한 증명은 모르겠고 대충 이런 논리로 풀었다.

E. BOJ 16766

일단 도착 시간을 정렬해놓고 보면 무조건 도착시간 순으로 인접한 애들을 한 버스에 몰아서 보내는게 이득이다. 따라서, 답 \(X\)를 고정시켜놓고 나면 그 \(X\) 값을 확보하기 위한 버스 최소 갯수가 얼마인지는 \(O(N)\)에 판별이 가능하다. \(X\) 값이 작아질 수록 필요한 버스 개수가 많아지므로, 이분 탐색을 이용해 \(O(NlogT)\)의 시간복잡도로 정답을 찾을 수 있다.

F. BOJ 15862

투 포인터로 해결할 수 있다. 각 유전자마다 필요한 개수를 저장해놓고 최대한 그 조건을 만족할 때까지 \(R\) 포인터를 뻗어보자. \(L\) 지점이 하나 증가하면 \(R\) 포인터도 이전보다는 더 오른쪽으로 가야만 조건을 만족할 수 있다. 따라서 \(O(N+K+R)\) 시간에 문제를 해결할 수 있다.

G. BOJ 2330

실험실 온도의 \(B_i\)값이 증가하는 순으로 정렬해놓고 보자. 각 미생물의 \(A_i\)부터 \(B_i\) 구간에 이미 설치된 실험실 개수를 빼고 추가로 설치되어야하는 걸 보면, \(R_i\)값이 작은것부터 보고 있으므로 여기서 최대한 오른쪽 끝에 실험실을 붙여서 설치하는게 이득이다. 앞으로 봐야할 나머지 미생물들은 최소한 얘보다 온도 구간이 큰 값에 있으면 있지 작은 값이 있지 않기 때문. 따라서 이 개수를 구한 다음 아직 실험실이 설치되지 않은 \(R_i\) 이하 위치들을 확인하면서 거기에 실험실을 설치해주면 된다.

특정 구간에 설치된 실험실 개수는 세그먼트 트리를 이용해 \(O(logN)\)에 계산이 가능하고, 아직 실험실이 설치되지 않은 위치들은 set 등의 자료구조를 이용해 \(O(logN)\)에 관리할 수 있다. 따라서 전체 시간복잡도 \(O(NlogN)\)에 문제를 해결할 수 있다.

H. BOJ 1692

내 위쪽 ~ 왼쪽 까지 칸들 비트마스크 상태로 관리하면, \(DP(state, x, y, p)\) 를 \((x,y)\)좌표에서 내 왼쪽칸이 좌우뒤집기를 했는지 여부(\(p\)), 비트마스크로 관리하는 상태가 \(state\)일 때 최소 연산 횟수로 정의하고 문제를 해결할 수 있다. 이렇게 풀 경우 \(O(2^16 \cdot N \cdot 16 \cdot 2)\)정도의 시간이 걸리므로 5초안에 돌기는 넉넉하다.

다만 메모리 제한이 작아서 토글링으로 구현해야 하는데 탑다운으로 짰다가 고치는 과정에서 좀 애를 먹었다.

BOJ 27657

고생 끝에 풀었다. 재밌는 문제.

merge sort를 응용해서 접근해보자. 배열을 적절한 그룹으로 나눈 뒤 두 번째 배열을 임시 배열로 이용해서 합쳐주는 식으로 \(O(NlogN)\)에 정렬하는 방법을 생각하기는 그렇게 어렵지 않다.

문제는 200만회라는 횟수 제한이 상당히 빡빡해서 적은 상수로 둘을 합치는 merge 과정을 생각하기가 굉장히 까다롭다는 점에 있다. 나는 아래와 같은 방법을 이용해서 상수를 줄였다.

이런 식으로 줄여주면 전체 180만회 정도의 연산으로 정렬을 할 수 있어 문제를 해결할 수 있다.