Code Monster 2017 인터넷 예선 후기

9.29 ~ 9.30 lg cns code monster 인터넷 예선을 치뤘다.

작년에 코드몬스터 홈페이지가 사라졌었는데 갑자기 부활하고 올해도 대회를 진행하려나보다~

카카오나 삼성보다 시상 인원은 적지만 그래도 노오오오오력해보고 다 경험이기 때문에 도전해보자~

5문제 출제되었고 개인적인 난이도로는

2 <<< 1 < 5 << 4 < 3  인 듯한다.

문제 해결 순서는 2 -> 4 -> 1 -> 3 -> 5 순으로 해결하였다.

1번은 문제가 열심히 설명하고 있는데 결국 

a 0

b 1 행렬 여러개 곱셈 연산했을 때 (2,1) 원소를 최대화 하는 문제이다.

행렬이 2개가 있을 때 더 크게 나오는쪽으로 배치해야 하는건 자명하다.

4개가 있고 왼쪽 2개 오른쪽 2개는 서로 잘 배치되었을 때 단순히 병합할 수 있는가? 라는 생각을 했는데 

사실 증명은 모르겠고 된다~~ 그래서 인접한 두 쌍을 비교하는 cmp함수만 만들고 sort 돌리면 된다.

2번은 쉬운 n^2 디피이다.

dag가 보장되므로 평범하게 잘 짜면 된다.

3번은 바로 n=3e5 고민하다가 오래걸렸는데, 먼저 n=500 생각해보면 

dp[i][j] = i를 루트로하고 적절히 커팅된 서브트리의 남은 크리스탈의 수가 j개가 되는 경우의 수로 정의하고

O(n^2) 트리 디피를 생각할 수 있다.

여기서 좀 더 생각해보면 j가 0일때, 1~k-1일 때, k일 때만 알면 되므로

dp[i][3]으로 줄일 수 있고

O(n)에 해결할 수 있다.

4번은 문제에 주어진 조건대로 그대로 구현하면 된다.

딱 하나 예외 해야되는게 삼각형 내부에 직각다각형이 포함된 경우이다. 이게 삼각형과 직각다각형이 교차하는 예에 포함된다.

나머지는 선분교차여부랑 접촉여부 판단하고 삼각형의 무게중심찍어서 이게 직각다각형 내부인지 아닌지 판별했다.

5번은 출발점 하나 정하고 다익스트라 돌렸을때 한 도착점에 대해서 필요없는 간선들을 저장할 수 있다.

이 간선들 중에 한 개만 사용하면 되는것이고, 뽑아야 하는 간선은 가중치가 작은것 부터 뽑아야 하는게 자명하다.

다익스트라 n번돌려서 뽑아야 하는 간선리스트 만들고 간선들 소팅하고 작은것 부터 뽑으면서 간선리스트에 존재하면 뽑고 아니면 넘어가는 식으로

구현하면 된다.

O(VElogV)에 해결할 수 있다.

아마 5개 풀어서 본선 갈 것 같은데 한 달 뒤 본선까지 노오오오오오오오력하여 좋은 결과 있으면 좋겠다~~~

띠요오오오ㅗ오오오옹~~~