제 3회 보라매컵 예선 Open Contest 후기

2회 이후로 소식이 딱히 없던 보라매컵이 무사히 3회까지 열렸습니다! 솔직히 저는 2회 이후로 아무 소식도 못 받았어서 그냥 2회가 마지막일 줄 알았는데, 언제보니 홍보 탭에서 제 3회도 열린다고 하더라구요. 제 1회때는 실제 대회 참가자로써, 제 2회는 운영진으로써, 그리고 이번 제 3회때는 오픈컨테스트 참가자로써 개근하게 되었습니다.

 

이번 대회 예선도 지난번 대회와 동일하게 서브태스크 문제들로 출제했습니다. 서브태스크 문제들만 출제했다는 뜻은 전체적인 문제 난이도 분포가 상당히 어려울 것일거라 예상했었습니다. 그래서 이틀동안 진행되는 실제 대회에서는 문제들을 효율적으로 잘 긁어 부분점수들을 최대한 따가는게 본선을 가기 위한 전략이었을 것이라 예상했습니다. (일단 저라면 저렇게 예선을 참가했을 것 같아요.)

 

그래서 저는 이번 대회를 실제 대회 참가자처럼 '효율적으로 잘 긁어서 순위권에 올라가보자!'라는 마인드로 참가했었습니다. 왜냐하면 제가 섭테 문제들만 존재하는 대회를 그리 많이 참가해보지 못해서 이 참에 연습하고자 했었습니다. 그리고 이렇게 연습하다보면 HackerCup이나 SCPC 등 부분 점수가 있는 대회에서도 좋은 결과를 볼 수 있을거라고도 생각했구요.

 

점수를 제일 효율적으로 긁어본다는 마인드로 참가한 결과는 아래와 같았습니다. 이제부터는 문제 순서대로 어떻게 풀었는지 후기를 남기도록 하겠습니다.

 

제 3회 보라매컵 예선 결과입니다. 대회에서 총 3등으로 마무리 했었습니다.

 

 

1. A번 : 대한민국을 지키는 가장 긴 힘 (+5) - 100/100

 

저는 DP로 풀었습니다.

 

대회가 있는 날이 제 동생 생일이기도 해서 외식하느라 처음에는 폰코딩으로 참가했었습니다.

 

일단 제일 머리에 떠오른 생각은 첫 글자부터 가능한만큼 순서대로 긁어보았을 때가 최적이 아닐까 생각했었습니다. 폰코딩이다보니 구현 실수로 1 WA를 상큼하게 적립하고 제대로 구현해보니 100점 만점에 64점을 얻었습니다. 결과를 보고 아무래도 다른 방법으로 푸는 문제인 것 같으니 일단 B번으로 넘어가서 B번을 먼저 풀었습니다.

 

이후에 생각을 해보니, dp[i]를 i번째 숫자가 묶이는 수의 제일 앞자리 숫자일때, dp[i+1] = min(dp[i+1], dp[i]+1), dp[i+2] = min(dp[i+2], dp[i]+1)을 만족하고, 세 자리 수까지 묶은 결과가 641 이하면은 dp[i+3] = min(dp[i+3], dp[i]+1)을 만족했었습니다. (물론 제일 앞자리 수가 0일수는 없어서 예외 처리도 해주어야 합니다.)

 

그렇게 구현해두고 if 문 조건을 잘못 적어서 3번 2점만 받다가 고쳐서 성불했습니다.

 

2. B번 : 사격 (+1) - 100/100

 

저는 Binary Search + Simulation으로 풀었습니다. 

 

문제를 보고 해석해보면 초기값이 크면 클수록 얻을 수 있는 점수도 커지게 됩니다. 따라서 초기값에 대해서 최대로 얻을 수 있는 점수는 monotone한 관계를 가지므로 Binary Search를 적용할 수 있습니다.

 

왜인지 모르게 예전에 제가 만든 BOJ 30205가 생각나는 문제였습니다. 그래서 그런지 정해를 쉽게 떠올릴 수 있었습니다. 그래도 제가 처음에는 폰코딩으로 제출해서 1 WA를 적립했었습니다. 컴퓨터 잡고 제대로 짜니 AC가 나왔습니다.

 

3. C번 : 훈련 (+6) - 66/100

 

좀 변형된 Knapsack DP가 정해일 것이라 생각합니다.

 

일단 바로 Knapsack DP를 어떻게 적용해야할 지 몰랐지만 Subtask 2는 그냥 Knapsack DP을 구현하면 되므로 Subtask 2번까지 먼저 긁었습니다. 그와중의 구현 실수 등의 문제로 인해서 6번째 제출에서 제가 원하던 66점을 얻을 수 있었습니다.

 

그리고 일단 넘어가서 나중에 F번을 푼 다음에 다시 돌아와서 손을 대보았으나... 대회가 끝나서 제출을 못했었습니다.

그래서 나중에 문제가 올라온 다음에 제가 마저 짜던 코드를 제출해보니 AC를 받긴 했습니다.

변형된 Knapsack DP가 맞았네요.

 

4. D번 : 축구 대회 (+0) - 10/200

 

이 문제는 DP 아니면 Bruteforcing 문제일 것 같습니다.

 

바로 어떤 태그인지도 떠올리지를 못하여 일단 제일 쉬운 섭테만 긁고 빨리 넘어갔습니다.

(그런데 대회 끝나고보니 저는 Subtask 2까지 긁은 줄 알았는데, Suibtask 1만 긁었네요... 엄;;;)

 

Bruteforcing 문제라면 BOJ 27282랑 비슷하게 조건을 잘 따져서 경우의 수를 줄이는 테크닉을 활용하는 문제일 것이라 생각합니다.

 

5. E번 : 시간 외 근무 멈춰!!! (+1) - 28/200

 

이 문제는 Greedy / Binary Search + Sorting + Simulation 문제일 것 같습니다.

 

'시간 외 근무 멈춰' 문제는 1회부터 꾸준히 나오는 문제였는데, 이 문제 시리즈의 기본적인 아이디어는 Greedy + Sorting 이었습니다. 그리고 이번 문제도 실제로 Greedy + Sorting 냄새가 나는 문제였습니다. 그런데 구현하는게 바로 떠오르지 않아 시간이 지체될 것이라 예상했습니다.

 

그래도 Subtask 2까지는 제 1회 문제랑 동일한 코드를 제출해도 풀리겠다는 생각이 들어서 일단 BOJ 27112 코드를 들고와서 수정해서 제출하니 Subtask 2까지는 긁혀 28점을 얻었습니다. 그러고 일단 F번을 풀러 갔습니다.

 

6. F번 : 물자 조달 (+6) - 300 / 300

 

저는 Offline Query + Floyd-Warshall + 정점 분할로 풀었습니다. (실제로는 Floyd-Warshall 응용입니다.)

 

일단 저는 대회를 시작하자마자 문제들을 전부 훑어보았습니다. 그때 이 문제의 제한조건을 잘못 이해해서 그래프의 구조가 트리인줄 알았습니다. 또한 문제에서 물어보는 것은 중간에 각 노드의 weight가 달라질 때 두 노드 간의 거리를 묻는 것이었습니다. 그래서 저는 처음에 이 문제가 HLD + Segment Tree로 쉽게 풀릴거라 생각했었습니다.

 

그래서 앞의 C,D,E를 긁기만 하고 왔는데... 보니깐 그래프는 일반 그래프였습니다. 그래도 일단 N의 조건이 작으므로 Floyd-Warshall을 활용하는 것은 확실해 보였습니다. 그래서 충분히 긁은 것 같은 C번, DP인지 Bruteforcing인지도 모르는 D번과 구현에서 감이 잘 안오는 E번을 제치고 먼저 F번을 풀기로 했습니다. (그리고 F번을 풀면 당시에 퍼솔도 가능했어서... 퍼솔이 고팠어요...)

 

먼저 Floyd-Warshall로 푼다면 어떻게 풀지 생각해보았습니다. 일단 각 정점별로도 가중치가 주어지는데, 이는 각 정점을 들오는 정점과 나가는 정점으로 분할을 해서 해소해야 될 것 같았습니다. 그리고 이제 두 정점을 이을 때는 나가는 정점 -> 들어오는 정점 이렇게 이어주면 될 것 같았습니다. 이후의 두 정점에 대한 최단거리는 Floyd-Warshall을 활용해서 찾았습니다.

 

이후에는 각 쿼리가 실행될수록 정점에 부하되는 가중치 값이 커져서 최단거리 값이 계속 커지므로 쿼리 순서들을 뒤집어 계속 가중치가 줄어드는 방향으로 계산하면 되겠다는 생각이 들었습니다. 만약에 특정 노드(A라고 합시다.)에 부가되는 가중치가 계속 줄어든다면 각 노드간의 최단거리는 원래 값이나 아니면 A를 거쳐서 가는 경로의 거리 둘 중의 하나가 됩니다. 

 

그래서 1번 쿼리가 들어오면 Floyd-Warshall을 개량해 O(N^2)로 업데이트를 해주었는데... O(QN^2)는 시간초과가 납니다. 그래서 제가 제출해보니 Subtask 2만 맞았었습니다. 이렇게 짜서 제출한 이유는 제가 또 조건을 잘못 읽었기 때문인데, 저는 각 기지별로 한 번씩만 공격하는 줄 알았는데 그게 아니라 특정 기지를 계속 공격하다가 타겟이 바뀌게 된다면 해당 기지는 다시 공격하지 않는다는 것이었습니다. (그래서 저는 Subtask 3번의 조건이 이해가 안 됐었습니다.) 만약에 기지마다 한 번씩만 공격한다면 모든 쿼리들을 실행 시켰을 때에 1번 쿼리에 대한 시간복잡도는 O(N^3)이라 뚫렸을 겁니다.

 

그래서 저는 쿼리들을 역으로 처리하면서 공격하는 기지가 바뀌면 그때만 변형된 Floyd-Warshall로 업데이트, 아니면 평상시에는 현재 계산된 최단거리 vs 현재 공격하는 기지를 거쳐서 가는 거리를 계산해서 2번 쿼리에 대한 답을 구하는 식으로 구현했습니다. 그렇게 되면 모든 쿼리들을 처리하는 시간복잡도도 O(Q + N^3)이 됩니다. 그렇게 해서 제출하니 AC를 받았습니다. 그런데 스코어보드는 이미 프리즈된 상태라서 제가 퍼솔인지도 몰랐습니다.

 

나중에 대회가 끝나고나서 제가 F번을 퍼솔했다는 것을 알게 되었습니다. 한 번도 못 해본 퍼솔을 보라매컵에서 그것도 제일 어려운 문제에서 해서 매우 기뻤습니다. 다만, 제가 이 대회에서 조건이나 지문을 제대로 안 봐서 WA를 맞는 등 기초적인 실수도 많이 있어서 그 점들은 반성해야 하겠습니다. 참가자 입장으로써 문제 퀄리티도 괜찮아 재밌게 풀었습니다. 특히나 DP를 좋아하면 매우 재밌었을 것 같아요. (무려 6문제들 중 3문제(A,C,F)가 DP...!)