BOJ 랜덤 마라톤 후기

이번에 Solved.ac이 시즌 4를 맞이하면서 새로운 기능이 생겼습니다. 바로 랜덤 마라톤이라고 일종의 주간 미션입니다.

랜덤 마라톤은 말 그대로 일 주일 단위 랜덤디펜스를 한다고 생각하면 됩니다. 총 8 문제가 여러 난이도 분포에 맞추어 주어지며 일 주일 내로 해당 문제들을 푼다면 추가 별조각을 얻을 수 있습니다.

 

Solved.ac 내부적으로 랜덤디펜스를 돌릴 수 있는 기능이 있으면 좋겠다고 생각했는데, 이런 기능이 나타나서 매우 흥미로웠습니다. 이를 통해서 저도 좀 더 PS에 흥미를 다시 가질 수 있고 또 조금 침체되어있는 듯한 분위기도 좀 환기시킬 수 있지 않을까라는 기대도 해봅니다. 

 

아무튼 잡소리는 여기까지 하고 제가 받은 마라톤 코스와 각 문제에 대해서 푼 후기를 남겨보도록 하겠습니다. 제가 받은 문제리스트는 아래와 같았는데, 궁금해서 F번은 미리 풀어보았습니다.

 

B1 ~ G2

 

지금 이 글을 쓰는 시각은 6월 18일 23:15로 나머지 문제들을 한 번 달려보도록 하겠습니다.

 

A : Cued In (Solved : 23:25)

Greedy + Math + Case-working(?) 문제였습니다.

빨간 공의 개수 만큼 제일 높은 점수의 공을 여러번 치고 빨간 공이 다 빠지면 나머지 공들을 전부 치면 됩니다.

Snooker가 뭔지 몰라서 이해하는 데 좀 시간이 걸렸네요;;

 

B : ポスター (Poster) (Solved : 23: 36)

Implementation 문제였습니다.

칸을 돌린 후에 색칠하든 칸을 색칠한 다음에 돌리는 것은 같습니다.

따라서, 해당 포스터를 0, 90, 180, 270도로 회전을 시키고 그리고자 하는 포스터와 차이가 최대한 적은 걸 답으로 고르면 됩니다. (물론 회전 시키는 데 시간도 포함하구요.)

일본어 문제도 나올 지 몰랐는데;; ChatGPT 덕분에 풀 수 있었습니다. 그와 별개로 좋은 문제라고 느꼈습니다.

 

C : 징검다리 건너기 (large) (Solved : 23:51)

Parametric Search로 풀었습니다.

K를 파라미터로 두어 최솟값을 찾으면 되는데, 특정 K값에 대해서 1번째 칸에서 시작해서 N번째 칸으로 도달하는 경우가 존재하는 지를 파악하면  됩니다.

처음에는 DP로 풀려다가 Parametric Search도 가능해보여 선회했는데 DP로도 풀 수 있었더라구요... 연습을 더 해야겠습니다.

그와 별개로 징검다리를 건널 때 뒤로도 갈 수 있는 걸 허용하여 DSU를 활용하도록 더하면 좀 더 재밌지 않았을 까 합니다. (물론 DSU로 풀 수 있다는 건 제 생각일 뿐 실제로 증명하진 않았습니다. 그런데 대강 O(N^2)로 돌들 끼리 이동할 수 있는 경우들을 undirected edge로 보아 그래프로 표현했을 때 1번 칸에서 N번 칸까지 갈 수 있는지 파악하면 되므로... DSU로도 풀 수 있을 것 같아요.)

 

D : NIKO (Solved : 00:35)

Bruteforcing + Implementation + Case-working으로 풀었습니다.

문제를 보고 어떻게 풀지 감이 잘 안 와서 고민을 매우하였습니다. 일단 문제 형태를 보았을 때 가장 먼저 떠오르는 건 bruteforcing이나 greedy로 풀 것 같다라는 생각이 들었습니다. 실제로 보라매컵에서 bruteforcing 문제 느낌도 났었으니깐요. 그런데, 이게 어느 부분을 bruteforcing 할 지는 잘 감이 안 왔습니다. (3^22로 모든 선수의 포지션을 결정 짓는 작업만 해도 1초가 훨씬 넘어가요...)

그러다가 문뜩 든 생각이 OV , VN, ON 인 선수들은 우선순위를 정하여 넣으면 되지 않을 까라는 생각이 들었습니다. 예를 들어 OV 선수를 보았을 때 V에 자리가 남아있으면 V에, 남아있지 않는 대신 O가 남으면 O에 넣는 식으로 우선순위를 bruteforcing하면 되지 않을까라는 생각이 들었습니다. 그래서 그렇게 풀어보니 실제로 문제가 풀렸습니다.

궁금해서 정해를 보았는데, 정해는 OV, VN, ON 각 선수들 중에서 몇 명을 O/V/N으로 보내고 나머지 몇 명을 다른 자리로 보낼지를 Bruteforcing해서 푸는 거라고 합니다. 제 풀이도 나름 비슷하게 풀었네요.

 

E : Risk (Solved : 01:09)

BFS 문제였습니다.

BFS 문제인 건 파악했는데... Input 포맷을 해석하는 것과 Output 포맷을 해석해서 맞추는 데가 좀 힘들었습니다.

문제 내용은 그냥 BFS로 최단거리 구하는 무난한 문제였습니다.

 

F : 작업 (예전에 풀었음)

Topological Sorting + DP로 풀었습니다.

작업들 간에 순서가 존재하고 모든 작업을 끝내는 데 걸리는 최소시간 구하기... ACM Craft 등에서도 많이 봤던 Topological Sorting + DP 문제였습니다.

다만, 제가 간과한 점이 있는데 이 문제에서는 Topological Sorting이 사실상 이미 되어있는 상태로 입력이 주어지기 때문에 그냥 1번부터 N번 작업 순차적으로 돌아가면서 DP 테이블을 채워도 됩니다. 그래서 그냥 DP로 풀어도 되었습니다.

 

G : Dragon Maze (Large) (Solved : 01:34)

BFS + DP 문제였습니다.

제일 우선적으로는 최단경로를 보아야 하므로 이는 BFS로 찾을 수 있습니다. 그런데, 우리는 힘이 최대화 되는 최단경로를 보아야 하므로 DP[y][x] : (y,x)까지 갈 때에 얻을 수 있는 최대 힘 이렇게 DP 테이블을 세워서 이를 저장해야합니다. 갱신 방법으로는 BFS로 해당 칸을 발견했을 때 i) 처음으로 발견했거나 ii) 아니면 발견했는 데 지금 발견한 경로도 최단거리일 경우 에 DP[y][x] = max(DP[y][x], DP[curr_y][curr_x] + power[y][x]) 이렇게 갱신해주면 됩니다.

그래프를 좋아해서 그러는지는 몰라도 해당 문제도 좋은 문제라고 생각합니다. (여담이지만... G3에 재밌는 문제들이 많은 것 같아요.)

 

H : 갈래 제곱 - 문제를 보니 적분식을 아는가를 물어보면서 문자열 파싱 + 구현 위주의 문제인 걸 파악했습니다. 아마... 오른쪽에 있는 식을 적분하여 왼쪽 식이 나오는지 직접 구현하는 방법으로 푸는 것 같긴한데, 제가 좋아하는 유형이 아니라서 패스했습니다. 

 

그래서 이번 주 제 마라톤 기록은 아래와 같습니다.

H번 일부러 안 풀긴 했지만... 혼자 안 풀어서 뭔가 그렇네요 ㅠ

 

오랜만에 이렇게 몰아서 문제를 풀어보니 재미있었습니다. 확실히 많이 쉬면서 실력도 좀 녹슬은 것 같습니다. 매일 1 문제씩 풀었는데 맨날 브론즈 실버만 풀어서 그런지 골드 문제들은 푸는데 시간이 좀 걸렸네요 ㅠㅠ 그래도 문제 셋도 복귀차 풀기도 좋았습니다. 그리고 문제들도 나름 가벼웠구요.

 

다만, 이번 마라톤을 풀면서 약간 아쉬웠던 점도 있었습니다. 우선은 문제 푼 사람 수에 대한 커트라인도 정할 수 있으면 매우 좋았을 것 같습니다. 제가 풀었던 문제들 상당 수가 푼 사람 수가 100명이 넘어가지 않았습니다. 그러면 해당 문제에 대해서 참고할 수 있는 솔루션이 매우 적어져서 못 풀었을 경우에 복기하기가 매우 어렵습니다. 실제로 제가 뭣도 모르고 실랜디를 돌렸을 때 본 BOJ 7475번은 못 풀어서 어떻게 푸나 한 번 인터넷에 찾아보았는데도 솔루션이 나오지 않았습니다. (그래서 해당 문제는 아직도 못 풀었습니다. 특히나 NEERC 2003에 나온 엄청 옛날 문제라 그런지... 공식 홈 솔루션도 안 보여요... 그래도 어디 중국 사이트에 솔루션이 올라온 것 같긴 합니다.) 그래서 문제 푼 사람의 수를 좀 더 많은 문제들을 추천해주면 좋을 것 같습니다.

 

이상 BOJ 랜덤마라톤 후기였습니다. 이제부터 다시 공부 열심히 해보겠습니다.