2018년 문제를 2021년이 되서야 푼다는 게 뭔가 뒤쳐지는 것 같아서 좀 그렇다 ㅎㅎ.. 카카오가 주최한 대회니만큼 문제에서 얻을 가치가 많다고 생각하여 풀게 되었다.

A. 상금 헌터

내가 제출한 코드

굉장히 쉬웠다. 처음에는 점화식을 세워서 풀어볼까 하다가 If 문으로 무식하게 짜는 것이 시간적으로 효율적이라 판단하였다.

적당한 노가다는 옳다!

B. 인형들

내가 제출한 코드

이것도 정말 하찮은 문젠데.. 내가 더 하찮았나보다. 처음에 문제를 잘못 읽은 줄 모르고 계속 오차 범위에서 틀리는 줄 알았는데 k개 이상이라는 걸 캐치하지 못하고 있었다..

이 부분을 수정하니 정작 오차 범위는 전혀 문제가 없었다.. 또한 \(N\), \(k\) 값이 여유있어서 무지성 브루트포스로 풀 수 있었다.

항상 문제는 꼼꼼히 읽자!

C. 숏코딩

내가 제출한 코드

이 문제는 알고리즘은 어렵지 않았는데,, 생각할 부분이 참 많았다.

생각해야 될 것들

1. 우선 파싱을 잘하자.
2. ’==’ 으로 연관되어 있는 것들은 union-find 로 묶어준다.
3. 같은 그룹에서는 ‘!=’ 로 연관되어 있어서는 안된다.
4. 한 그룹에 상수가 2개 이상이면 무조건 거짓이다.
5. 등등.. 엄청 많다.

알고리즘이 어렵지는 않아서 괜찮았는데 다 잘 구현해놓고 parsing하는 부분에서 substr 을 써서 \(O(N^{2})\) 을 만들어버렸다.

나는 포인터 느낌으로 substr 이 \(O(1)\) 인 줄 알았는데 그 길이만큼 걸린단다. ㅠ

그래서 파싱 하는 부분만 싹 바꿔주니 잘 됐다.

D. 부스터

내가 제출한 코드

C를 풀기전에 D가 티어가 더 낮아서 먼저 풀었다. 여기서부터 내 한계를 맛 보고 답지를 열심히 참고하였다. ㅎㅎ;

첫 번째 시도

처음에 든 생각은 어느 한 체크포인트에서 다른 체크포인트로 갈 수 있다면 간선을 연결하여 그래프를 만들고 BFS or DFS로 풀면 되지 않을까 싶었다. 그런데 문제는 시간복잡도가 \(O(N^{2} + Q \cdot N ^ {2})\) 이라는 것이다.

두 번째 시도

그래프를 만들 때, 더욱 간단한 방법이 있다. 어떤 체크포인트 \(i\) ,에서 \(j\) 로 가는 데 필요한 최소 HP는

이다. 따라서 \(i\) 와 \(j\) 를 연결하는 edge를 하나로 미리 계산하지 말고 weight가 \(\|X_{i}-X_{j}\|\) 인 것, \(\|Y_{i}-Y_{j}\|\) 인 것, 총 2개의 edge를 만든다. 어차피 우리는 그래프 탐색을 할 때, weight가 작은 edge를 선택할 것이기 때문이다!

구현이 더욱 간단해지겠지만, 아직 문제는 시간복잡도에 있다..

세 번째 시도

위 그래프에서 X 좌표 차이로만 이루어진 간선들만 고려해보면, 이는 모든 점들을 X축 수직선에 내렸다고 볼 수 있다. 예제 데이터를 예시로 들면 1번에서 4번까지 잇는 간선은 필요가 없다. 어차피 1번에서 2번, 5번, 3번을 거쳐 4번으로 갈 수 있기 때문이다.

이처럼 인접하지 않은 두 점의 간선은 지울 수 있으며, 이를 Y 좌표에 대해서도 하면, 우리는 총 \(2\cdot (N-1)\) 개의 간선만 가지게 된다.

처음 그래프의 간선을 만들 때도, sort하여 인접한 점들에 대해서만 edge를 만들면 된다.

이제 시간복잡도는 그래프를 만드는 데 \(O(N\log{N})\) , 모든 쿼리를 해결하는 데 \(O(Q \cdot N)\) 이다. 아직 시간복잡도가 크다..

네 번째 시도

쿼리를 HP에 대해서 sorting을 하는 아이디어를 어떻게 생각할까.. 사람들 참 대단하다!

HP가 작은 순으로 쿼리를 해결하면 좋은 점이 있는데, 예를 들어 HP가 2일 때, 갈 수 있다면, HP가 2 이상일 때도 갈 수 있다. 즉, 갈 수 있는 집합의 크기가 점점 커지므로 이를 union-find 로 해결하면 된다! union-find 를 너무 오랜만에 들어서 관련 문제도 하나 풀어보았다.

구현

알고리즘 구현은 굉장히 수월했는데 계속해서 뜬금없이 런타임 에러가 났다..(이러면 수월했다고 하면 안되려나..?) 정말 하루를 꼬박 삽질하다가 문제점을 찾았다.

sort할 때, compare 함수를 따로 주었는데 다음과 같았다.

bool compare(pii a, pii b){
    return a.second <= b.second;
}

저 망할 놈의 등호가 있으면, \(a\) 와 \(b\) 가 같은 값을 가질 때, 무한 swap이 일어나서 런타임 에러가 난다는 것이다. 정말 수십번의 제출 끝에 문제점을 알았고 이 무지한 사람을 구원해준 @Altair_Vega, THANK YOU!

후기

E번 문제를 풀다보니 5월이 다 지나갔다.. 한 달 동안 6문제도 못풀겠어? 했는데 생각보다 시간이 없다는 점, 내가 게으르다는 점을 파악하지 못했다.. 게다가 문제 티어가 다이아이다보니 먼저 겁먹고 시도하기가 어렵더라..

조금 쉬운 문제로 자신감을 되찾을 필요가 있어보인다. 6월에는 더 나은 모습으로 나아가야지! 화이팅!