즐기자는 마음만으로 참가했는데, 시작 2분 전부터 갑자기 긴장되더라구요ㅋㅋ

우선 문제들을 차례대로 읽고 쉬운 것부터 차근차근 풀어나가자는 마음가짐으로 임했습니다.

A번을 보니 너무 쉬워서 곧바로 짜고, B를 읽다보니 A가 맞았더군요. B를 다 읽고, 특별히 어려운 건 아니고 구현이 조금 까다로울 수 있겠다 싶어서 그 다음 문제 C번을 읽었습니다.

C번을 보니 단순한 dfs/bfs 문제여서 얼른 짜고 D번을 봅니다.

N이 100 이하이고 M이 10000이하여서 d(i, j) = "i번 정점까지 왔을 때, 사용한 비용이 j일 때의 최단거리"로 정의해서 DP로 풀려고했습니다. 그런데 문제가 발생합니다. 문제를 자세히 읽어보면 단방향 그래프인데, 양방향으로 이해했었습니다. 그래서 Dijkstra를 돌면서 DP 비슷하게 풀어서 제출했더니 틀립니다. 2~3분 동안 소스코드를 다시 읽고 문제를 읽어보니 단방향입니다. 고쳐서 맞았습니다.

스코어보드를 한 번 보았습니다. 상위권인데, 다른 사람들은 F를 풀었는데 전 안풀었더라구요.

E번은 건너뛰고 F번을 먼저 봅니다. dfs로 짜면 풀릴 거 같은데, 구현이 복잡해보입니다. 그런데 이런 문제를 이렇게 빨리 풀었을 리가 없을 거 같다는 생각에 좀 더 생각을 해보기로 합니다. 각 고기들이 뒤집히기만 하면 되고 다른 조건이 없습니다. 그냥 주어진 입력 전체를 오른쪽으로 대칭하게 뒤집어 보았습니다. 문제의 답이 됩니다. 곧바로 짜고 맞았습니다.

스코어보드를 보니 1등과 문제 수는 동일하고 패널티 차이로 3등이었습니다. 이젠 문제를 찬찬히 다 읽고, 상황을 정리해야겠다고 생각했습니다.

G번 - H번 - I번 - E번을 읽었습니다. E번이 쉬워보이는데 코딩이 귀찮아보입니다. G번을 생각하기로 합니다. 시그마(A(i)) = n이고 시그마(i * A(i)) = n인 성질을 이용해서 DP로 풀려다가 말립니다. 예를 들어, A(0) = 2라면, 뒤에서 A(i)에 0을 2번을 써야하는데 처리가 안되는 걸로 보아 접근이 틀렸다고 판단했습니다. 스코어보드를 보니 조승현군(ainta)가 풀었습니다. ainta도 사람이라는 믿음에 일단 백트랙킹을 짜 봅니다. 15까지 출력해보니 규칙이 보입니다. 짜서 맞췄습니다.

스코어보드를 확인하니 그대로 3등이라서 패널티가 중요한 거 같다는 판단에, 솔루션이 나온 E를 어서 짜기로 합니다. n*m 그리드인데 중간에 m을 n으로 쓰는 실수를 한 것을 빼고는 꽤나 빠른 시간에 풀어서 맞추었습니다. 스코어보드를 보니 2등이 되었습니다. 여유롭게 생각해도 되겠다는 판단에 H번을 고민합니다. 공간복잡도는 n^2에 되지만 시간복잡도가 n^3인 풀이가 나왔습니다. 일단 짜보니 예제가 나옵니다. 더 줄이려고 노력했지만, 실패했습니다.

I번을 고민합니다. Naive하게 4^n은 TLE이므로 생각을 해봅니다. 힘과 마력을 구분해서 생각할 수 있습니다. 힘을 i번 선택하면 마력을 n-i번 선택하므로 힘의 기댓값 * 마력의 기댓값으로 계산하면 되겠다는 판단을 했습니다. 2^n 솔루션이므로 일단 짭니다. 예제가 안 나옵니다. 문제를 잘못이해해서 n번 정확히 된 후에 공격을 하는 줄 알았습니다. 얼른 고쳐서 제출을 해봅니다. TLE입니다. 2^(n-1) 솔루션을 짭니다. 제출합니다. 또 TLE입니다. 최대 데이터 100개를 넣고 제 컴퓨터에서 돌려보니 5초 정도 걸렸습니다. 여러가지 최적화를 시켜주고 다시 제출해보지만 역시나 TLE...

이게 정해가 아닐거라는 생각을 1시간 반 동안 삽질을 하다가 생각해내고, 다른 풀이를 떠올려보지만 잘 안됩니다. 짤 줄 아는 B번을 짜는 게 이득이라는 생각에 B번을 짜봅니다. 생각보다 코딩이 말려서 꽤나 시간이 걸렸습니다. 제출해보지만 또 TLE입니다.

J번을 봅니다. 인덱스트리로 뭔가 될 것 같은 느낌에 짜다가 말립니다. 이럴 바에 B를 고치는 게 낫다는 판단을 합니다. B번을 메모이제이션 비슷하게 구현하다가 대회가 종료되었습니다.

1시간 41분에 6문제를 맞추고 더 이상 푼 게 없었습니다. 스코어보드를 보니 다른 분들도 저처럼 실수를 많이 하셨는지, 운이 좋아서 8등으로 대회를 마쳤습니다. 다른 형들, 친구들과 풀이를 얘기하다보니 제가 많이 부족했다는 걸 느꼈습니다. 솔루션 발표를 들으면서 나름 이해가 된 것 같았는데 기차에서 H번을 다시 코딩하다보니 또 잘 안되더라구요ㅠㅠ 열심히 공부해야겠다는 생각이 들었습니다.

좋은 문제들 제공해주신 출제진분들, 풍선 달아주시고, 밥이랑 물도 주시느라 많이 힘드셨던 스탭분들 모두 진심으로 감사합니다.

특히 백범기념관이라는 뜻 깊고 쾌적한 장소에서 대회를 개최해주신 백준이형과 째님 감사합니다.

BOJ에서 게시판에서만 뵙던 분들이랑 친해지고 싶었는데, 대회 끝나고 그냥 예약해두었던 ktx타고 집에 와버렸네요ㅠㅠ

긴 글 읽어주셔서 감사합니다. 올해 ICPC 리저널이나 내년 코더스하이에서 뵈요! ^^