0909

오늘은 2018 서울대 프로그래밍 경시대회 오픈 컨테스트에 참가했다. div1을 참가할까 2를 참가할까 하다가 하루종일 머리도 아프고 해서 좀 쉬운 문제나 느긋하게 풀자 생각하고 div2에 참가. 총 8문제를 풀었고, 몸 상태가 안 좋아서인지 코딩 실수를 너무 많이 했다. 대회 끝나고 대회 중에 못 풀었던 한 문제까지 추가로 풀어서 총 9문제.

아래는 푼 문제에 대한 간단한 정리.

A. 5차 전직

주어진 n개의 숫자를 정렬한 다음, 맨 처음부터 순서대로 k개씩 더해나가면 되는 문제였다. 간단한 문제.

B. 시그널

완전 구현 문제였는데, 그냥 일일히 따서 풀었으면 오히려 패널티가 적었을 텐데 그렇게 하기 싫어서 다른 방법으로 풀다 실수를 많이 해서 여러 번 틀렸다. 이런 문제는 풀 때마다 어떻게 푸는 게 가장 좋은 방법일지 고민이 좀 많이 된다. 

C. 화살표 연산자

상당히 골때리는 문제였다 ㅋㅋ n = 1인 예외를 생각하기가 좀 힘들어서 몇 번 틀렸다.

D. 팬이에요

비교적 간단한 기하 문제였다. 주어진 선분들 중 길이가 가장 긴 애들에 대해서 원점을 기준으로 각도를 구해 준 다음, 인접한 각도간의 차이 중 가장 큰 것을 출력해주면 되는 문제.

E. 작은 큐브러버

8개의 1x1 큐브 조각이 주어진다. 각 큐브는 인접한 세 면에 색깔이 칠해져 있는데, 이 1x1 큐브 조각 8개를 합쳐서 2x2 큐브를 만들 수 있는지 묻는 문제다. 깔끔하게 구현하는 게 좀 까다로운데, 가능한 색깔 배열 6!을 전부 테스트 해보는 게 그나마 좀 구현하기 쉬운 것 같다.

F. 실버런

간단한 DP라고 생각했는데 굉장히 생각하기 힘든 예외가 하나 있었다. 0.5지점에서 시작하는 건 금방 생각했는데, x,y가 전부 0.5인 좌표에서 시작해야 valid하다는 것을 떠올리는데 시간이 좀 오래 걸렸다. 그리 어렵지 않으면서 생각을 많이 요구하는 재밌는 DP 문제였다.

G. PPAP

P에서 시작해서, 임의의 P를 PPAP로 바꾸는 연산을 반복했을 때 주어진 문자열을 만들 수 있는지 묻는 문제이다. 유사한 문제가 굉장히 많고 풀어본 적 있어서 쉽게 풀었다. P 만 있어도 답이라는 걸 생각 안해서 한 번 틀림

H. 달빛 여우

다익스트라 응용 문제. 늑대와 여우가 있는데, 늑대는 매 간선을 여우가 달리는 속도의 두배 속도/ 절반 속도를 번갈아가며 달린다. 이걸 간단하게 하려면 기본적으로 모든 간선의 길이를 *2해준 다음, 늑대의 상태를 두 개로 분리해서 한 번 /2, 한번 *2 해주면 쉽게 계산할 수 있다. 근데 머리가 오락가락해서 다익스트라 구현을 이상하게 하는 바람에 두세번 틀렸다.

J. Cherrypick

재밌는 문제였다. n(<=1000)이 주어지고, 가로세로 n 크기의 숫자 판이 주어진다. 여기서 어떤 가로세로 x크기의 정사각형을 골랐을 때 그 정사각형의 가치는 (정사각형 내에서 가장 큰 값) - x^2으로 정의된다. 모든 칸에 대해서, 그 칸을 포함하는 사각형의 가치중 가장 큰 값을 골라서 출력하는게 문제.

어떻게 해도 n^3아래로 줄이기가 힘든데, 주어진 숫자판에서 나올 수 있는 숫자의 최대 크기가 1000이라는 점을 이용하면 쉬워진다. 숫자 최대 크기가 1000이라 가로세로 크기 sqrt(1000) 이상의 사각형의 가치는 절대 0이상이 될 수 없다. 따라서 모든 칸에 대해 최대 32 사이즈 범위에서의 최댓값을 전처리 해두면 32 * 1000 * 1000시간에 풀 수 있다. 대회 중에 sqrt(1000)까지만 보면 된다는 것을 떠올렸는데 그걸 이용해서 실제로 구하는 걸 잘못 생각해서 결국 못 풀었다.