11월의 문제 풀이 - (3)

11/21 ~ 11/30에 푼 문제들입니다.

문제의 풀이가 포함되어있으니 유의하세요.

 

---

11/22

BOJ 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

Platinum 4

 

#dfs   #sweeping

 

깊이를 기준으로 스위핑을 하면 된다.

$0 \le i \le j \le \log_2{N}$인 $i, j$에 대해, 깊이 $i$ 이상 $j$ 이하의 모든 점을 탐색하며 최대 연속합을 구하자.

이 스위핑+탐색이 문제에서 요구하는 직사각형을 그려보는 것에 해당한다.

연속합은 트리를 inorder 순서로 펴서 구해도 되는데, 본인은 금광 테크닉으로 구했다.

---

BOJ 16877 - 핌버

Platinum 3

 

#sprague_grundy

 

스프라그-그런디 정리로 해결하면 된다.

mex를 set으로 구했더니 시간 초과를 받아서 set을 안 쓰고 어떻게 할까 한참 고민했다.

---

11/23

BOJ 2834 - 박스 정렬

Platinum 4

 

#constructive   #permutation_cycle_decomposition

 

빠지기 쉬운 함정은 각 사이클을 연산 하나에 처리하는 것이고, 나도 이것 때문에 5WA를 기록했다.

왜 틀렸지 생각하다가 다음과 같은 반례를 하나 생각해냈다.

$1\, 3\, 4\, 2\, 5\, 7\, 8\, 6\, 9\, 11\, 12\, 10\, 13$

이 케이스는 사이클의 개수가 3인데도 최소 연산 횟수는 2이다.

이걸 보고 사이클을 합칠 수 있는 방법을 생각해냈고, 연산 횟수는 어떤 케이스에서도 2를 넘지 않는다는 것을 관찰할 수 있었다.

---

BOJ 24505 - blobhyperthink

Platinum 4

 

#segtree

 

dp로 접근하는 방법을 생각해보자.

$dp[i][k]$를 $A_i$를 끝 원소로 갖는 길이가 $k$인 증가 수열의 개수라고 하자.

그러면, $1 \le j < i$이고 $A_j < A_i$인 $j$에 대해 $dp[i][k]$는 다음과 같다.

$dp[i][k] = \sum{dp[j][k-1]}$

이 때, 초깃값 $k = 1$에 대해 $dp[i][1] = 1$이다.

$k \le 11$에 대해 각각의 세그먼트 트리를 만들어주면, 11개의 세그트리로 문제를 해결할 수 있다.

작은 원소부터 세그에 넣어주면 된다.

---

BOJ 2049 - 가장 먼 두 점

Platinum 3

 

#convex_hull   #rotating_calipers

 

볼록 껍질 상에서 두 포인터로 rotating calipers를 구현하면 된다. 돌아가는 동안에 생기는 두 점의 거리 중 최댓값을 출력하자.

---

BOJ 13728 - 행렬식과 GCD

Platinum 4

 

#number_theory

 

작은 크기에 대해 행렬식을 구해보면 $1,\, 2,\, 3,\, 5,\, 8,\, 13,\, \cdots$이 나온다.

정리하면 $D(i) = Fib(i+1)$임을 알 수 있다.

따라서 $\gcd(D(i), D(N)) = \gcd(Fib(i+1), Fib(N+1))$이고, 이는 $Fib(\gcd(i+1, N+1))$와 같다.

---

11/24

BOJ 2699 - 격자점 컨벡스헐

Platinum 5

 

#convex_hull

 

널리 알려진 방법대로 볼록 껍질을 구하고, 문제의 조건에 맞게 정렬시켜 출력했다.

(이전에는 Graham Scan으로 볼록 껍질을 구했었는데, lower hull과 upper hull로 나누어 구하는 방법을 배워서 이걸로 쓰려 한다. 직접 구현해봤을 때 후자가 훨씬 이해가 잘 되고 더 간결한 것 같다.)

---

BOJ 10254 - 고속도로

Platinum 2

 

#convex_hull   #rotating_calipers

 

위의 2049번 문제와 동일한데, 거리 대신 두 점을 직접 출력하는 문제다.

(CCW를 구할 때, integer overflow를 처리 못해서 맞왜틀에 30분 정도 시달렸다.)

---

11/26

BOJ 4925 - Minimum Spanning Tree

Unrated

 

#mst   #parsing   #stack   #implementation

 

인접 행렬 형태로 주어지는 그래프 $G$와 $Q$개의 트리 $T$를 입력으로 받아서, 각각의 $T$가 $G$의 MST인지 판별하는 문제이다.

 

$G$의 MST가 존재하는 상황만 생각해보자. (존재하지 않으면 모든 $T$에 대해 답은 NO라서 고려할 필요가 없다.)

트리 $T$가 다음 조건을 모두 만족하는지 확인하면 된다.

1. 트리의 모든 간선은 $G$에 존재하는 간선이어야 한다.
2. 트리의 모든 간선의 가중치 합은 $G$의 MST 가중치와 같아야 한다.
3. 트리에는 $1$부터 $N$까지의 점이 한 번 씩만 등장해야 한다(?).

입력 형식이 재귀적으로 주어져서, 스택 등을 이용해 트리의 간선을 뽑아내야 한다.

 

입력 형식이 매우매우 더럽다. C++ 유저로서, 트리 입력 부분이 상당히 힘들었다.

---

11/27

BOJ 30844 - Плодотворное сотрудничество

Gold 1

 

#math

 

$0, 6, 8, 9$에 대해 닫힌 영역이 각각 $1, 1, 2, 1$개 생긴다.

$1$부터 $N$까지의 수에서 등장하는 $0$, $6$, $8$, $9$의 개수를 세주면 된다.

유사한 문제가 있다. 예전에는 풀지 못했었는데, 이번엔 다행히 풀었다.

---

BOJ 7354 - 트리의 순서

Platinum 5

 

#tree   #divide_and_conquer

 

정점이 $N$개인 바이너리 트리의 개수를 $cnt[N]$이라고 하자.

이 트리는 정점의 수가 각각 $i, N-1-i$인 두 개의 서브트리로 반드시 나뉘어진다. $(0 \le i < N)$

따라서 $cnt[N] = \sum \limits_{i=0}^{N-1} {cnt[i]\times cnt[N-1-i]}$이다.

 

이제, $K$번째 바이너리 트리의 정점의 개수를 $cnt$로부터 구할 수 있게 되었다.

현재 트리가 정점이 같은 다른 트리 중에서 $g$번째 트리라고 하면, 왼쪽과 오른쪽 서브트리에 대해 각각의 노드 수와 $K$를 특정할 수 있다.

 

이 과정을 재귀적으로 수행하며 트리를 구성하고 출력해주면 된다.

---

BOJ 9527 - 1의 개수 세기

Gold 2

 

#math

 

이 문제도 틀려놓고 1년 이상 방치했던 문제인데, 생각난 김에 풀었다.

위의 30844번 문제 등과 거의 같은 문제인데, 이게 조금 더 쉽다.

---

11/29

BOJ 3090 - 차이를 최소로

Platinum 2

 

#parametric_search   #greedy

 

인접한 수의 차이의 최댓값을 변수($x$)로 두고 이 값으로 가능한 최소를 찾기 위해 이분 탐색을 하면 된다.

여기까지는 쉬운 발상이지만, $T$번 안에 모든 수의 차이를 $x$ 이하로 만들 수 있는지를 판별하는 것이 난이도가 높은 이유이다.

주어진 배열 내에서 최솟값에는 절대로 연산을 수행하면 안 된다는 것을 인지하자.

 

우선, 배열을 왼쪽에서부터 오른쪽으로 탐색하며 $A_i$를 $max(A_{i-1} + x, A_{i+1} + x, A_i)$로 만들어주자.

이렇게 하면, 최솟값을 기준으로 오른쪽에 있는 친구들은 모두 차이가 $x$ 이하로 맞춰진다. 하지만 왼쪽에 있는 친구들은 아직 맞춰지지 않았을 수도 있다.

반대로, 배열을 오른쪽에서부터 왼쪽으로 탐색하며 같은 작업을 수행해주면 왼쪽 친구들도 모두 차이가 $x$ 이하로 맞춰지게 된다.

---

11/30

BOJ 18233 - 러버덕을 사랑하는 모임

Gold 5

 

#greedy   #bruteforcing

 

가능한 조합 $2^{N}$가지 경우를 모두 확인하면 된다.

각각의 경우에서 가능한 값의 하한과 상한이 정해지고, 이를 적절히 분배해주면 된다.

---