딱히 열심히 할 생각이 없었는데 4등한 기념으로 리뷰글 씁니다.
우선, 난이도 배분이 상당히 적절하게 되어있었습니다. 간단한 입출력 문제부터, 어느 정도 심화적인 개념이 필요한 문제까지 고루 분포해있었다고 생각합니다. 다이아 이상의 문제들도 익숙하신 분이라면 아니겠지만, 플레티넘 정도의 문제를 연습하고 계신 분들까지라면 풀어보시는 것도 좋을 듯한 문제셋입니다.
A. 고무오리 디버깅
문제의 컨셉과 풀이 모두 굉장히 아기자기한 문제입니다.
문제를 풀며 단 한 가지 걱정이 되었던 것은 한글 입출력인데, 영문자를 취급하듯 코드를 짜도 AC를 받을 수 있었습니다.
변수에 남은 문제의 수를 기록하며 처리하면 됩니다.
B. 사과나무
2차원 배열에서의 prefix sum을 사용하는 문제입니다.
우하단의 끝칸을 고정하고 가능한 한 변 길이를 모두 시도하면 총 $O(N^2)$개의 칸에 대해 $O(N)$번의 시도를 하게 되며, 각 시도에 소모되는 시간은 $O(1)$이므로 총 시간 복잡도는 $O(N^3)$이 됩니다.
C. 거스름돈이 싫어요
우선 숫자의 크기를 줄이기 위해 모든 입력되는 분수를 기약분수로 만듭니다.
그 후 분모의 lcm을 구해 통분하고, 분자의 gcd를 구합니다. 구한 분자의 gcd는 정답의 분자가 되고, 통분된 분모는 정답의 분모가 됩니다.
혹시 모르니 한번 약분해주면 lcm, gcd를 구하는 각 과정은 $O(N)$에 해결할 수 있으므로 AC를 받을 수 있습니다.
D. 베스킨라빈스 31
두 사람이 베스킨라빈스 31 게임을 할 때는 기본적인 룰에서 4n+2꼴의 수까지 부르고 멈추면 이길 수 있음이 잘 알려져 있습니다. 이것의 증명은 상대가 먼저 시작할 때 항상 상대와 내가 한 턴에 부른 수의 개수 합이 4개가 되게 할 수 있음을 이용하므로, 우리도 이 점을 이용해보아야 할 것 같습니다.
A개의 수를 부를 때, 상대가 먼저 시작한다면 늘 상대와 나를 합쳐 A+1개의 수를 부를 수 있습니다. 30을 부르는 사람이 이기고, 플레이어는 후공입니다.
30이 (A+1)의 배수가 아니라면 상대는 시작할 때에 30%(A+1)개의 수를 부름으로써 반드시 승리할 방법이 존재합니다. 반대로, 30이 (A+1)의 배수라면 후공은 반드시 승리할 방법이 존재합니다. 따라서 출력해야할 수는 n 이하의 (30의 약수-1)인 수입니다.
E. 보스몬스터 전리품
구현이 조금 귀찮을 수 있는 문제입니다.
각 플레이어의 위치를 찾고, bfs를 통해 보스몬스터까지의 최단거리를 구해줍니다.
이후 도달시간 순으로 정렬하여 스위핑으로 계산하면 간단하게 해결할 수 있습니다.
F. 랭킹전 대기열
vector 안에 vector을 넣으면 쉽게 해결 가능합니다.
J. 악덕 영주 혜유
크루스칼 알고리즘으로 MST를 구하고 MST의 지름을 구해주면 됩니다.
소감
어느 정도 문제를 풀다가, 마지막 문제인 J번의 난이도를 보고 의욕을 잃어서 G, H, I는 문제를 읽지도 않았습니다. 순위 변동표에서 1등이었던 적이 있는걸 보면 계속 풀어 1등 할 수도 있지 않았을까 싶은데 딱히 그럴만한 의욕은 안 났었네요…
오랜만에 대회에 참가해서 그런지 재미 있었습니다.