PS 일지 (3)

마지막 수정 시각: 2023-01-16 14:26:40

GoodBye BOJ 2022에 참가하고, PS 소모임 Prompt412에서 토요일마다 진행하는 연습 라운드를 풀었다.

GoodBye BOJ 2022

대차게 말아먹었다고 생각했는데, 어쨌든 목표였던 본선은 진출해서 마음을 놨다. 최근의 대회에서 자주 나오는 유형의 문제를 잘 못 푸는 거 같다. 한동안 BOJ에서 랜덤 문제만 풀고 대회 문제들을 잘 풀지 않다보니 추세를 따라잡지 못 하고 있는 느낌. 올해는 코드포스 참여라든가 열리는 대회에서 일정 난이도 이상의 문제들은 전부 풀고 넘어가기 같은 걸 좀 하는게 좋겠다는 생각이 들었다.

이 대회도 EF번 업솔빙을 해야하는데 귀찮아서 미루는 중... 본선 전에는 풀고 넘어가야할 것 같은데.

B. BOJ 27066

합치는 과정에서 전체 수의 평균이 배열의 최댓값보다 커질 수 없다. 따라서 문제의 답은 항상 주어진 수열의 최댓값 이하임을 알 수 있다. 여기서 다시 주어진 수열에서 두번째로 큰 수를 생각해보자. 이 수보다 값을 크게 만들려면, 최대한 큰 수와 두 번째로 큰 수를 같이 선택해야만 한다(나머지 수는 골라도 항상 값이 감소하므로). 그런데 두번째로 큰 수와 가장 큰 수를 같이 선택하면 이 수가 제일 큰 수가 되어버리므로, 이게 중위값이 될 수가 없어진다(중위값이 되려면 모든 수를 다 같이 선택해야만 하게 된다). 반면 두번째로 큰 수보다 작은 수를 전부 선택하면 항상 두번째로 큰 수가 중위값이 되게 할 수 있다. 따라서, 전체 평균과 두번째로 큰 수 중에 더 큰 값이 답이 된다.

C. BOJ 27067

모든 수가 뒤에서 앞 방향으로 변형되었으며, 변형된 단계도 서로 다르다는 점에 주목하자. 주어진 수열에서 맨 뒤 위치를 기준으로 최소 2개는 원래 그 위치에 해당하는 수다. 변형된 단계가 서로 다르기 때문에 맨 뒤에 있는 수 중에 둘 이상이 앞으로 당겨갈 수는 없기 때문이다. 따라서, 2개 이상이 일치하는 수가 원래 그 위치에 해당하는 수가 된다. 이 수를 제외하고, 나머지 수에 대해서 같은 과정을 반복하면 마찬가지의 논리가 성립하게 된다. 따라서 이 과정을 통해 \(O(N)\)에 답을 복구할 수 있다.

D. BOJ 27068

답 \(K\)을 고정하고 답에 대한 이분탐색을 하자. 선명도를 \(X\)로 바꿀 수 있고 원래 모든 선명도는 항상 \(X\)이하의 수이다. 여기서 어떤 위치 \(U\)를 선명도 \(X\)로 바꿨을 때, \(V\)도 선명도 \(X\)로 바꿔야만 답이 \(K\)이하가 된다면 \(U\)와 \(V\) 사이에 간선이 있는 것으로 생각해보자.

이런 조건으로 그래프를 그리고, 맨 처음에 주변과 선명도 차이가 \(K\) 이상 나는 모든 위치를 선택하면 이 위치와 간선이 연결된 다른 모든 정점들도 같이 선택해주어야만 한다. 이런 개수는 DFS로 계산 가능하므로, 전체 시간 복잡도 \(O(NMlogX)\) 에 문제를 해결할 수 있다.

Prompt412 Round 179

H번을 못 풀고 끝난 뒤에 업솔빙했다. G번 문제같은 유형에서 항상 헤매게 되는데 어떻게 해야 빨리 풀 수 있는지 모르겠다.

B. BOJ 3231

\(i\)가 나타난 위치를 \(Pos_i\)라고 하자. \(Pos_{i+1} \lt Pos_{i}\) 일때마다 한 번 다시 앞으로 돌아가야하므로, 이러한 상황이 발생할 때마다 답을 \(1\) 증가시켜주면 \(O(N)\)에 문제를 해결할 수 있다.

E. BOJ 16323

각 원소를 크기 순으로 정렬하고나면 항상 \(b_i * 2 \le b_{i+1}\) 이 성립한다. 따라서, \(b_1 + b_2 + \dots + b_i \lt b_{i+1}\) 이므로, 가장 큰 수부터 보면서 \(b_i \lt s\) 면 선택하는 걸 반복하는게 답이 된다. \(b_i\)를 선택하지 않으면 어차피 그 아래의 수들을 다 더해봤자 \(b_i\)보다 작기 때문에 합 \(s\)를 만들 수 없기 때문이다. 따라서 \(O(NlogN)\)에 문제를 해결할 수 있다.

F. BOJ 4442

답은 결국 두 좌석표중 하나랑 일치하는 형태가 된다. 결국 두 좌석표와 서로 다른 부분에서 어느 한쪽에 앉은 쌍의 차이 수를 줄이면 다른 한쪽에서 차이 수가 늘어나서 두 좌석표중 하나와 일치하는 걸 선택하는게 최선이 된다. 이러면 두 좌석표 간의 쌍 차이 수를 구하는 문제가 되고 이는 곧 배열의 역위 개수를 구하는 문제와 같은 문제가 되므로, 세그먼트 트리를 쓰거나 분할 정복을 쓰거나 하는 등의 방법을 통해 \(O(NlogN)\)에 문제를 해결할 수 있다.

G. BOJ 3007

수식을 잘 써서 접근해보면 실마리를 찾을 수 있다. 원본 배열을 \(a\), 입력으로 주어진 배열을 \(b\)라고 하자. 이 때,

\(a_n + a_1 + a_2 = b_1\)

\(a_1 + a_2 + a_3 = b_2\)

...

이 성립한다. 여기서 연속한 두 식을 빼면, \(a_n - a_3 = b_1 - b_2, a_1 - a_4 = b_2 - b_3 \dots\)과 같은 차이로 표현되는 식을 구할 수 있다. 이 식을 이용해서 \(a_1 = 0\)으로 두고 차이만 가지고 \(a_i\) 값들을 표현해보자. \(a_1 - a_4 = x, a_4 - a_7 = y\) 같은 식들을 연계해서 정리하면 모든 수들을 \(a_1\)과의 차이로 표현할 수 있게 된다.

이렇게 되면 연속한 세 수를 합한 것으로부터 \(a_1\)값을 구할 수 있고, 이 값으로부터 연쇄적으로 모든 \(a\)값을 복구하는게 가능해진다.

다만 여기서 신경써야하는 예외가 있는데, \(n\)이 \(3\)의 배수일 경우 모든 수들이 세 칸 간격으로 서로 다른 싸이클을 형성해서 각 수를 \(a_0\)에 대한 차이로 표현할 수 없게 된다. 이 경우 세 싸이클을 각각 \(a_0, a_1, a_2\)에 대한 차이로 표현하면 이 차이의 합이 항상 일정하게 더해져야한다는 점을 이용해서 비슷하게 \(a\)배열을 복구할 수 있게 된다. 마지막 케이스를 잘 정리하지 못해서 한참 헤맸다.

H. BOJ 11982

먹히지 않는 그리디를 먹힌다고 생각하고 잘못 구현한게 문제였다. \(l_i\)를 \(0..i\)번째까지 전부 다 터뜨리기 위해 필요한 최소 힘, \(r_i\)를 \(i...n\)번째까지 전부 다 터뜨리기 위해 필요한 최소 힘이라고 하자. \(l,r\)이 구하는 방법이 크게 다르지 않으므로 \(l\)을 구하는 방법만 찾으면 \(r\)도 동일한 방법으로 계산할 수 있다.

\(l_i\)를 계산할 때, 어떤 지점 \(x\)를 잡아서 \(x..i\)를 한번에 터뜨린다고 생각하자. 이때 필요한 비용은 \(p_i - p_x\)와 \(l_x + 1\)중에 더 큰 값이 된다. 또, 항상 \(l_{i-1} \le l_i\)가 성립함도 알 수 있다.

이 때 어떤 \(l_x\)에 대해 \(p_i - p_x\)가 \(l_x\) 이상인 가장 큰 \(x\)를 고르는게 이득이다. 이것보다 \(x\) 위치를 더 왼쪽으로 둔다면 \(p_i - p_x\)에 답이 지배되고, 더 오른쪽으로 둔다면 \(l_x\)값이 더 커지고 그 값에 답이 지배되기 때문이다.

이러한 \(x\)의 위치는 또 \(i\)가 증가하면 같이 증가하기 때문에(\(x_i \le x_{i+1}\)), \(x\) 위치를 투포인터로 관리해주면 \(l,r\)을 전부 \(O(N)\)에 구할 수 있다.

이제 최종적으로 중간 어디에 떨어트리는게 최선인지를 생각해야하는데, 이 중간에 터뜨리는 것도 처음에 터뜨리는 폭탄이 \(a\)부터 \(b\)까지를 커버한다고 생각해보자. 이 경우, 폭탄은 항상 이 구간의 가운데에 떨어뜨리는게 이득이고 나머지 구간에 대해서는 각각 \(l[a] + 2, r[b] + 2\)만큼의 비용이 소모된다. 따라서 세 값 중 가장 큰 값이 이 경우의 답이 된다.

처음에 \(a,b\)를 전체 구간으로 잡아놓고 다음 스텝을 생각해보자. 답이 감소하려면, \(l[a+1]\)과 \(r[b-1]\)중 값이 더 작은 쪽부터 확장하는게 이득이다. 두 값중 어느 한쪽에 의해 답이 결정되는 경우 항상 최대한 작은 값을 고르는게 이득이기 때문이다(그렇지 않은 경우는 어차피 가운데 구간에 의해 답이 결정되므로 좌우 크기는 상관이 없고).

따라서, \(O(N)\)에 전체 문제를 해결할 수 있다.