결과부터 말하자면 B Large를 제외한 모든 문제를 해결했고, 133위로 순조롭게 Round 2에 진출했다. R1A는 시험을 쳤지만 1000등 밖이라 떨어졌고, R1B도 칠 예정이었는데 과 MT랑 날짜가 겹쳐서 가서 어떻게든 쳐보려고 노트북을 들고 갔지만 인터넷이 안 되서 결국 R1C에서 통과하게 되었다.
A
A는 Battleship이라는 게임에서 파생된 간단한 게임 문제로, 두 사람이 최적의 해로 플레이할 때 게임이 얼마나 오래 지속되는지를 묻는 문제였다. small은 1차원, large는 2차원상에서 문제를 해결해야 하지만 배의 방향이 고정되어 있어 풀이가 크게 달라지지는 않는다. 한 번 위치를 부를 때 배가 있을 수 있는 가능성이 W개 줄어든다는 것을 관찰하면 쉽게 탐욕 알고리즘을 세울 수 있다.
28:37 AC
B
무한한 수의 원숭이들에게 타자기를 하나씩 쥐어 주고 무한한 시간이 흐르면 그 중 한 마리는 셰익스피어의 햄릿을 완성시킬 것이다.
B는 위의 유명한 농담에서 파생된 문제다. 목표 문장과 원숭이의 타자기가 주어지고, 원숭이가 몇 글자를 누르는지가 주어지면 원숭이가 목표 문장을 완성하는 횟수의 기대값을 구하는 문제였다. 일단 풀이는 생각이 났지만 동적 계획법과 문자열 매칭 알고리즘을 응용하는 지나치게 복잡한 풀이라 우선은 전부 만들어보는 naive한 방법으로 small만 해결했다.
38:56 AC
C
C는 화폐 개혁을 통해 사용 가능한 동전 개수를 최소로 추가하면서 특정 금액을 지불할 수 있도록 만드는 문제였다. 보자마자 떠올린 알고리즘이 맞았고, 목표 금액이 아주 큰 경우에서 실수한 것 때문에 한 번 WA를 받고 통과했다.
54:16 AC
전체 후기
문제를 풀면서 예상했던대로 B Large는 훨씬 쉬운 풀이가 존재했다. 나는 한 번 길을 잘못 들면 잘못된 풀이에 계속 빠져 있는데, 그걸 잘 파악해서 B Large를 빠르게 넘기고 C를 푼 게 이번 라운드의 성공 요인이라 생각한다. 100점이 아닌 사람들 중에서는 1위를 했고, 라운드 초반에는 잠깐이나마 Top 10에도 올라갔었기 때문에 성공적이었다고 생각한다.
이번에 못 풀었던 B Large 복습하고 R2에서도 좋은 결과를 얻어 올해는 꼭 티셔츠를 받고 싶다!