[2020 브랜디 코딩대회 코드네임. B] 브랜디 코딩대회 2차 후기

2차 대회는 9월 5일 14:00 ~ 17:00에 진행되었다.

1차땐 워낙 문제가 쉬워 이번엔 좀 어려워지긴 하겠지 예측을 했지만 예측한 것보다 훨씬 어려운 문제들이 출제되었다.

 

1차 후기를 쓴 것과 마찬가지로 각 문제를 어떤식으로 풀었는지, 어떤 알고리즘으로 풀었는지에 대해서만 언급하겠다.

 

1번 : 100점

알고리즘 : 완전탐색

처음엔 지문이 너무 안 읽혔다. 계속 읽어봐도 안읽혀서 내가 생각한대로 짜봤더니 WA가 나왔다. 좀 더 고민을 하고 있다가 1번 문제에 관해 공지가 올라왔는데 그 이후로 파악을 해서 풀었다. 제대로 이해했을 때 떠올린 풀이는 바로 완탐이였다. (모든 경우를 완탐을 하면 TLE, 하지만 문제 조건에 맞춰서 특수(?) 상황에 대해 완탐은 AC)

 

2번 : 100점

내가 사용한 알고리즘 : SPFA

1번 지문 이슈때문에 그런지 2번이 더 쉽게 느껴졌다. 범위를 보고 맘 편히 SPFA로 돌렸다. TLE 뜨면 다른 알고리즘(다익)으로 푸려고 했는데 AC를 받아서 그냥 넘겼다.

 

3번 : 100점

내가 사용한 알고리즘 : Mo's Algorithm

이 문제를 보자마자 느낀 점은 "형이 여기서 왜 나와?" 였다. Mo's 알고리즘을 공부한 이후로 각 종 알고리즘 대회에서 거의 못봤던 Mo's algorithm을 보게 되서 한편으로는 반갑기도 했다. 세그트리로 풀 수 있을꺼 같은 느낌이 들어서 도전을 해보려고 했지만 역시나 Mo's 알고리즘으로 푸는게 매우 편안하게 느껴졌다. 처음엔 버킷 사이즈를 작게 잡아서 TLE가 떴지만 바로 버킷 사이즈를 늘려줘 AC를 받았다.

 

4번 : 21점

이 문제를 읽고 멘붕에 빠졌다. 내가 알고 있는 알고리즘 지식을 총 동원을 해서 고민을 해봤지만 다 TLE가 예측되서 당황했다. 못 맞출것을 알고 최대한 점수를 긁었어야 했는데 그 생각을 못하고 최대한 푸려고 하다가 마지막으로 제출한 코드로 21점 밖에 못 긁었다. 나중에 비슷한 문제가 나온다면 꼭 다시 도전해보고 싶다.

 

푼 순서는 2번 -> 1번 -> 3번 -> 1번 -> 4번 이런식으로 문제를 도전했던 것 같다. 아쉽게 다 풀지는 못했지만 그래도 이 대회를 통해 실력이 조금 늘었다는 것을 느낄 수 있어서 기분은 좋았다.

 

 

 

다행히 상위 7위 ~ 16위 안에 들어서 입상을 수상을 하였다. 시상식에서 이름이 랭킹 순으로 적혀 있었다고 가정을 하면 입상에서 4번째에 있었으니 상위 10위인 것 같다. 상위 10위를 할 수 있었던 것을 생각해보면 킹갓 실력자 분들이 브랜디를 신청 못하신 분도 있고 브랜디 2차 대회때 SCPC 2차도 있어서 빠져서 가능했던거 같다.