[백준 | BOJ] Good Bye, BOJ 2021! 후기 및 풀이 (ABCD)

백준에서는 연말에 굿바이 백준, 연초에 헬로 백준(굿모닝 백준) 행사가 있다. 2021 백준 마무리할 겸 문제풀이.

 

Good Bye, BOJ 2021! 2솔브

대회에서는 2솔브, 끝나고 CD 업솔빙까지 했다.

 

A. 2021은 무엇이 특별할까?

$N$ 범위가 $10,000$이다. 소수를 쭉 늘어놓고, 두개를 미리 곱해두고 이분탐색해서 풀었다.

사실 이분탐색은 필요가 없는데. 원소 개수가 30개가 안 된다. 배열을 한 바퀴 돌 걸.

$N = 10,000$일 때 103까지 넣어둬야 하는데, 넣지 않아서 WA, 테스트한답시고 넣은 코드를 안 없애서 WA.

자잘한 실수를 많이 했다. 제출 전에는 꼭 체크하자.

 

B. 예쁜 케이크

대회 중에는 OEIS의 힘을 받아서 풀었다. 손으로 줄줄 쓰다가 뭔가 규칙이 있는 것 같아서 넘겼다.

증명은 아래와 같다.

$N = pq$ 인 $p$ 와 $q$ 가 있을 때, $2(p+q) \equiv 0 (mod\;3)$ 를 만족하는지를 묻는 문제이다.

$(p+q) \equiv 0 (mod\;3)$ 을 만족해야 하는데, 나머지의 순서쌍이 $(0, 0), (1, 2), (2, 1)$ 로 세 가지다.

$(0, 0)$인 경우, $p$ 와 $q$ 가 모두 3의 배수이므로, $N$ 은 9의 배수가 된다.

$(1, 2)$ 또는 $(2, 1)$의 경우에는 $pq$ 의 나머지가 2이므로, 3으로 나눴을 때 나머지가 2이면 된다.

즉 9로 나눴을 때 나머지가 0, 2, 5, 8이면 예쁜 케이크, 나머지는 아니다.

 

C. 성싶당 밀키트

처음에는 문제 이해하는데 시간이 걸렸고, 다 만든 코드를 시간초과 될 거라고 생각하고 제출하지도 않았다..

나중에 보니 $2\times10^9$ 이분탐색이 30정도밖에 안 되는데 왜 넘어갈 거라고 생각했는지 한심하다.

시간복잡도부터 한번 생각하고 코딩하자..

풀이는 생각보다 간단히 떠올렸다. 나이브하게 날짜에 대해서 이분탐색한다. 각 탐색마다 문제에서 주어진 $S_i \times max(1, x-L_i)$ 를 기준으로 재료를 정렬한다.

반드시 필요한 재료는 추가하고, 필요하지 않은 것들은 정렬해둔 뒤쪽부터 $K$ 개 뺀다.

재료를 뺄 수록 세균의 수가 줄어드니 최대한 많이 빼는 게 최적의 답을 구할 수 있다.

근데 이게 맞다.. 이분탐색 하는데 $log(2\times10^9) \approx 30$, 정렬하는 데 $NlogN$이니까 다 해서 $NlogN$ ..

대회 후에 제출했는데 WA. 이분탐색 고치고, 범위를 다잡아서 AC. (0이 될 수 있다...)

 

D. 횡단보도

그래프가 주어지고, 각 노드를 잇는 간선들은 정해진 시간에만 이동할 수 있다. (를 보자마자 다익스트라가 떠올랐어야 했는데)

처음에는 BFS / DFS를 가지고 풀려고 했지만 그대로 포기.

이 문제는 알고리즘 분류를 보고 풀었다. 

최단거리를 구한다. 간선의 가중치가 1 이상이니까, 경로 비용이 감소하지 않으므로 다익스트라를 적용할 수 있다.

문제는 시간을 어떻게 요리하느냐인데, 간선의 가중치는 입력받을 때 순서로 두었다. 우선순위 큐에 다시 넣을 때 지금까지의 경로 비용을 더해서 넣어주면 된다.

$1$ 번 노드에서 시작해서 $N$ 번 노드까지 가면 되고, 모든 노드는 직/간접적으로 연결돼 있으므로 통하는 경로는 적어도 한 개 이상 있다.

우선순위 큐에 $1$ 번 노드를 넣어둔다. 반복에서는 다음과 같이 한다.

현재 시각을 $M$으로 나눈 나머지가 가고자하는 간선의 가중치보다 작을 때, 신호를 한 바퀴 기다려야 한다.

크거나 같을 때에는 즉시 이동하거나, (가중치 - 나머지)만큼 기다린 뒤 이동하면 된다.두 가지만 분류를 한 뒤, 계산한 가중치가 더 낮다면 (더 빠르게 이동할 수 있다면) 갱신하고 큐에 넣어주면 된다.시간복잡도는 $O(MlogM)$.

 

문제가 재밌다. 좀 더 붙잡고 있을걸 같은 생각이 든다,, 다음 굿모닝 백준에서는 4문제는 풀어봐야지~