본문 바로가기

카테고리 없음

0909~0911 Problem Solving

시험기간에 들어가기 전 마지막 연휴 기념으로 최근에 문제를 많이 풀었습니다. 연휴가 끝나면 중간고사 전까지는 PS를 쉴 것 같습니다.

작성한 모든 난이도는 제가 문제를 해결할 당시 난이도 기준입니다.

BOJ 16225. 제271회 웰노운컵

더보기

모든 (A[i], B[i]) 순서쌍을 B[i]에 대한 내림차순으로 정렬하면, 2개씩 뽑았을 때 나는 반드시 오른쪽 것을 가져갑니다.

내가 가져갈 N/2개를 먼저 정한 후에 나머지 N/2개와 짝지어 준다고 생각합시다.

짝이 지어지기 위한 필요충분조건은 for all 1<=i<=N, 1~i번째 것들 중 내가 선택한 것의 개수가 i/2개 이하인 것입니다.

따라서 그리디하게 A[i]가 큰 것부터 보면서 위 조건을 충족하는 것을 가져가면 됩니다.

위 조건은 Segment Tree Lazy Propagation으로 관리해 줄 수 있고, 총 시간복잡도는 O(NlogN)입니다.

(위에서 설명한 풀이가 정해는 아니고, priority queue를 이용해 훨씬 쉽게 구현할 수 있습니다.)

BOJ 5530. JOIOI 탑

더보기

처음에는 그리디로 어렵지 않게 될 줄 알았는데, I를 맨 앞에 써야 할지 맨 뒤에 써야 할지 특정하지 못해서 그리디로 풀기 쉽지 않을 것이라 느꼈습니다.

매개 변수 탐색을 떠올렸습니다. 총 x개의 IOI와 JOI를 만들 수 있는지에 대한 결정 문제를 생각해 봅시다.

최대한 뒤에서 x쌍의 OI를 선택해줍니다. 그 다음에는 앞에서부터 보면서 J 또는 I가 나올 때마다 앞에 있는 OI부터 하나씩 그리디하게 매칭해줍니다. 이렇게 x개가 모두 매칭되면 가능, 아니면 불가능입니다.

이를 이용하여 이분 탐색으로 O(NlogN)에 해결할 수 있습니다.

(추가로 매개 변수 탐색을 사용하지 않는 O(N) 그리디 풀이가 존재한다고 합니다.)

BOJ 8211. Tree Rotations

더보기

문제 정의를 해봅시다.

공통 부모를 가지는 두 서브트리의 크기가 각각 l, r이라 합시다. 양쪽 서브트리에서 수를 하나씩 뽑은 l*r개 쌍 중 인버전의 개수 inv를 계산하고, 모든 부모에 대해 min(inv, l*r-inv)의 총합을 구해주면 됩니다.

한쪽 서브트리 내에 있는 1, 2, ..., n의 개수(순열이므로 최대 1)가 세그먼트 트리에 저장되어 있다고 하면, 반대쪽 서브트리 내에 있는 모든 수에 대해 그 수보다 큰 수의 개수를 합해서 inversion의 개수를 계산할 수 있습니다.

이때 small to large technique를 이용하여 큰 서브트리 내에 있는 1, .., n 개수를 저장하고 작은 서브트리에서 쿼리를 처리해주면 됩니다.

ETT를 사용해서 각 서브트리 내에 있는 원소를 알 수 있습니다. 재귀적으로 각 서브트리의 원소를 세그먼트 트리에 남길지 말지 결정하여 dfs를 하면 O(Nlog^2N)에 문제를 해결할 수 있습니다.

BOJ 8201. Pilots

더보기

투 포인터 느낌으로 r을 증가시킬 때마다 구간의 최솟값과 최댓값 차이가 t 이하가 되도록 l을 당겨주면 됩니다.

구간의 최솟값은 monotone deque를 이용하여 계산할 수 있습니다. 총 시간복잡도는 O(N)입니다.

BOJ 14589. Line Friends (Large)

더보기

웰노운 Sparse Table 문제입니다.

dp[i][j]를 i번 선분에서 2^j번 이동하여 갈 수 있는 가장 먼 점의 좌표로 정의합니다.

각 선분의 왼쪽 끝 점에서 오른쪽 끝 점까지 갈 수 있으므로, 이를 이용해 prefix max로 dp[i][0]를 계산할 수 있습니다.

쿼리 A, B 처리는 다음과 같은 방식으로 진행합니다.

두 선분이 겹치면 1을 출력하고, 아니면 R[A]<L[B]라 합시다.

L[B]보다 작은 조건에서 sparse table로 최대한 이동합니다. 이때 이동횟수를 k라 합시다.

한 번 더 이동해서 L[B]보다 크거나 같은 곳으로 갈 수 있다면 k+2를 출력하고, 아니면 -1을 출력하면 됩니다.

시간복잡도는 O(NlogN)입니다.

BOJ 8222. Distance

더보기

처음에 이 문제를 2^a * 3^b 꼴의 입력만 주어지는 경우부터 생각해 보면서 풀어보려고 했습니다. 그런데 a와 b가 조금 커지면, 이 문제는 2차원 평면의 각 점에서 가장 가까운 점을 구하는 다이아 1 문제가 되므로 이러한 접근 방식은 틀렸음을 직감했습니다.

 

1로부터 각 수까지의 distance를 d[i]라 둡시다. 이때 a와 b 사이의 distance는 d[a] + d[b] - 2d[gcd(a, b)]가 됩니다. 이를 적용하기 위해서 각 a_i의 모든 약수에 d[a_i]를 저장한다는 아이디어를 생각했습니다.

이 방법을 구체화하면 다음과 같습니다.

1부터 10^6까지의 수에 대해 각각 pair<int, int>를 넣는 set을 총 10^6개 만듭시다.

전처리로 각 a_i에 대해 자신의 약수의 set에 {d[a_i], i}를 넣습니다.

각 a_i에 대해 d(a_i, a_j)가 최소인 j를 찾기 위해, 모든 약수 p를 보면서 p의 set에 들어가 있는 pair 중 second값이 i가 아니면서 first값이 가장 작은 것을 (존재한다면) 찾고, d[a_i] + first - 2d[p]과 현재 답 중 더 작은 값으로 답을 갱신시킵니다.

이렇게 그대로 구현해서 내면 MLE가 납니다. 각 set에는 3개 이상의 원소가 들어갈 필요가 없음을 이용해서, 가장 작은 2개만 남기고 관리해주면 됩니다.

시간복잡도는 O(N*약수 개수)입니다(set의 크기가 3을 넘지 않으므로 삽입, 삭제 시간은 거의 상수입니다).

BOJ 10075. 친구

더보기

제가 본 문제 중 세 손가락 안에 들어갈 만큼 아름다웠던 문제입니다.

문제의 핵심 아이디어는 사람 n-1부터 거꾸로 생각하는 것입니다.

사람 n-1의 host를 p라 하겠습니다.

 

1. 프로토콜 IAmYourFriend로 추가했을 경우

사람 n-1을 선택하면 p를 선택하지 못합니다.

답에 사람 n-1의 신뢰도를 더해주고, p의 신뢰도에서 사람 n-1의 신뢰도를 빼줍시다.

사람 n-1을 선택하지 않고 p를 선택하는 것이 최적일 수도 있기 때문에 p의 신뢰도에서 사람 n-1의 신뢰도를 빼주는 것입니다. 이렇게 하면 나중에 p를 선택했을 경우 답에는 p의 신뢰도만이 더해지게 됩니다.

그러나 위 과정에서 p의 신뢰도가 음수가 되었을 경우, p의 신뢰도를 0으로 바꿔주어야 합니다. 어차피 음수 신뢰도를 선택할 이유가 없기 때문에 답에 영향을 주지 않는 0으로 바꾸어 줍시다.

0으로 바꾸어주지 않으면 2, 3번의 처리 과정에서 충돌이 발생하기 때문에 바꾸는 것입니다.

 

2. 프로토콜 MyFriendsAreYourFriends로 추가했을 경우

사람 n-1과 p의 친구관계는 같습니다. 즉, p를 선택할 수 있다면 사람 n-1도 선택할 수 있고 그 반대도 성립합니다.

따라서 이 경우에는 사람 p의 신뢰도에 사람 n-1의 신뢰도를 더해주면 됩니다.

 

3. 프로토콜 WeAreYourFriends로 추가했을 경우

사람 n-1과 p 중 최대 한 명만 선택할 수 있고, 나머지 친구관계는 동일합니다.

따라서 p의 신뢰도를 p의 신뢰도와 사람 n-1의 신뢰도 중 최댓값으로 갱신하면 됩니다.

 

위 스텝을 반복한 후 답을 출력하면 됩니다.

BOJ 1741. 반 나누기

더보기

간선 여집합 그래프에서 컴포넌트 크기를 모두 구해주면 되는 문제입니다.

모든 정점 중 차수가 가장 낮은 정점을 찾아봅시다.

union find를 사용하여 그 정점과 연결되어 있지 않은 모든 정점을 union해줍니다.

그 정점과 연결되어 있는 정점(union되지 않은 정점)들에 대해서는 naive하게 해 주면 됩니다.

이때 차수의 총합은 2M/N이므로 naive하게 살펴보아야 하는 정점은 최대 2M/N개입니다.

따라서 총 시간복잡도는 O(N+(2M/N)*N) = O(N+M)입니다.