업다운 랜디 (2) - 230612

P4부터 시작했다.

 

18138. 리유나는 세일러복을 좋아해 (P4, 17:58)

 

이분 매칭 기본 문제이다. 코드를 안 보고 짠 데다가, 짧은 DFS 코드가 기억이 나지 않아 에드먼드 카프를 짜서 시간이 좀 걸렸다.

 

20560. 맛집 탐방 (P3, TLE)

 

갓문제들의 산실인 나코더 송년 대회 문제이다. 비슷한 문제(정확히는 이 문제의 하위호환)를 얼마 전에 풀었어서 첫 번째 조건은 어렵지 않게 구할 수 있었다. SCC로 만든 DAG에서 위상 정렬의 결과가 유일하면 된다. 문제는 두 번째였는데, 대충 생각했을 때 첫 번째 조건에 더해 DAG의 모양이 체인이면 된다는 사실을 알 수 있었다. 그리고 그대로 구현했더니 무수한 WA의 늪에 빠지고 말았다. 구현량이 좀 있어서 시간이 부족하기도 했고, 원래 한 번 말리면 뇌가 굳는 편이라 그대로 시간 제한인 45분을 넘기고 말았다. 답을 까보니 두 번째 조건에는 체인에 속하지 않는 하나짜리 노드가 있을 수 있었다. 이를 반영해서 고쳤더니 몇 번 더 틀린 후 맞았다. 조금 침착하게 코딩을 시작할 필요가 있는 것 같다. 위에서 언급한 비슷한 문제가 P3이라 P2로 기여했다.

 

25589. 푸앙이와 코인 (P4 -> P5. 9:56)

 

처음에는 그물의 모양이 직사각형인줄 알고 조금 당황했다. 정사각형이니 가능한 개수는 \(O(N^3)\)이고, 각 정사각형에 대한 비용은 누적합을 통해 \(O(1)\)에 구해줄 수 있다. 그물이 두 개여야 한다는 부분은 두 정사각형은 항상 어느 세로선이나 가로선에 대해 분리될 수 있다는 점을 이용하면 된다. DP로 각 방향에서 오는 영역에 포함되는 정사각형 비용의 최댓값을 구해준 후 계산할 수 있다. 글로 정리하니 꽤 긴데, 풀 때는 어렵지 않다고 생각해서 P5를 줬더니 티어가 내려갔다.

 

13303. 장애물 경기 (P3, 23:30)

 

골드 상위 쯤에서 흔히 찾아볼 수 있는 스위핑 문제이다. 이 문제, 그리고 이 문제와 세팅이 비슷해서 관찰을 빨리 했다. 각 선분의 시작, 끝 좌표에 대한 다음 도착 선분은 항상 정해져 있다. 이는 y좌표 순서대로 스위핑을 잘 해주면 구할 수 있다. 이를 구한 후에는 x좌표 순서대로 보면 일종의 DAG가 된다. 수평 이동 거리는 어차피 모두 같으니 제외하면, DP로 각 지점에 도달하는 최소 수직 이동 거리를 구해줄 수 있다. 구현을 좀 이상하게 해서 시간도 오래 걸리고 코드 길이도 길어졌다. 이런 문제에서 깔끔하게 짜는 법을 연습할 필요가 있는 것 같다.

 

다행히 구데기스러운 문제가 잘 걸리지 않는 것 같다. 다음에는 P2부터 시작한다. 여기까지 풀었을 때 백준 1999솔이라, 2000번째 문제로 찍어둔 문제를 푼 후 랜디를 다시 시작할 예정이다.