GCJ 2017 Quals 후기

들어가며

대회 덕분에 오랜만에 또 문제풀이 코딩을 했다. 전부 풀긴 했는데 시간을 좀 오래 썼다. D에서 코딩 미스가 한 번 있었다. 문제풀이를 좀 쉬었을 때 풀 수 있는 문제 풀은 크게 안 변하는데, 코딩 속도나 풀이를 떠올리는 속도가 좀 줄어든 것 같다는 기분을 느꼈다.

풀이

Problem A. Oversized Pancake Flipper

같은 위치에서 두 번 뒤집는 것은 불필요하므로 왼쪽부터 하나씩 뒤집어보면 된다. O(N^2)으로 Large input이 풀리기 때문에 특별히 자료구조를 쓸 필요도 없다.

A.cpp

Problem B. Tidy Numbers

입력이 tidy한 경우 그대로 출력한다. 입력이 tidy가 아닌 경우 112333445552 형태로 증가하다가 감소하는 지점이 있을텐데, 그 감소하기 직전의 반복되는 부분(여기서는 555)의 첫 숫자를 1 낮추고, 그 뒤쪽을 전부 9로 채우면 된다.

B.cpp

Problem C. Bathroom Stalls

시뮬레이션으로 풀 수 있다. 당연히 한 명씩 넣는 건 아니고, 연속된 구간의 크기와 개수를 이용해 시뮬레이션 하면 지수적으로 수를 줄여나가면서 O(log K)만에 해결 가능하다. 한 가지 관찰이 필요한데, 반씩 줄여 나가는 방식으로 시뮬레이션 하더라도 어떤 시점에서 구간의 크기의 종류가 최대 두 종류라는 사실이다. (n) -> (a, a+1) -> (b, b+1)과 같이 연속한 두 수에 대해서만 관리하면 되고, atomic하게 처리하지 않는 경우에도 최대 네 종류만 관리하면 된다. 탐색 최대 크기가 작아 굳이 Balanced Binary Tree를 쓸 필요는 없었지만 코딩하기 귀찮아서 set을 발라서 해결했다.

C.cpp

Problem D. Fashion Show

굉장히 마음에 드는 문제였다. 독립된 두 개의 문제를 하나의 문제인 것처럼 섞어서 꼬아 놓았는데, 두 제한조건이 사실 독립이라는 것을 깨달아야 해결할 수 있다. 임의의 같은 가로줄/세로줄에 있는 두 모델을 골랐을 때 둘 중 최소 하나가 +여야 한다는 말은, 바꿔서 말하면 +가 아닌 칸은 같은 가로줄/세로줄에 최대 하나 존재할 수 있다는 말이다. 비숍 배치 문제처럼 가로세로, 대각선 조건에 대해 각각 이분매칭으로 해결한 뒤 겹치는 칸은 o로, 겹치지 않는 칸은 x와 +로 설정해 주면 된다.

D.cpp

댓글 남기기