알고리즘/국대 멘토교육

대회실습 3 (5.21)

kdh9949 2017. 5. 21. 18:49

<US Open 2014>


문제를 한 번 훑어 본 결과 1번이 뭔가 쉬워 보였고, 2번은 예전에 풀었던 다른 문제와 굉장히 비슷해 보였다. 그래서 그 두 개를 먼저 풀기로 했다.

1번은 최대 8개의 다른 색의 점 중 일정 구간의 점들을 택하는데, 어떤 k종류 이상의 색의 점을 모두 같은 개수씩 가져가는 구간 중 가장 긴 구간의 길이를 구하는 문제이다. 8개 중 k개 이상의 색을 고르는 경우를 모두 해 보면서(약 2^8가지 경우가 있다) 각 경우에 대해 map을 이용하면 선택한 색들이 모두 같은 갯수만큼 들어간 구간들을 O(NlogN) 시간에 구할 수 있는데, 마지막 부분에서 약간 애매하게 TLE가 난다. 새로운 풀이를 잠시 생각해 보았으나 더 좋은 풀이가 생각이 나지 않아 2번으로 넘어갔다.

2번은 레이저 광선이 지나가는 경로에 거울 하나를 놓아 목표 지점으로 레이저를 보낼 수 있는 거울의 위치의 가짓수를 구하는 문제로, 시작 지점(방향 고정)과 도착 지점(4방향 모두 가능)에서 각각 레이저 광선을 쏘았다고 할 때 둘이 만나는 지점에 거울을 놓으면 항상 처음 지점에서 목표 지점으로 레이저를 보내는 경로가 된다는 것을 알 수 있다. 레이저 시뮬레이션은 좌표압축 + lower_bound 등으로 적절히 O(NlogN)에 할 수 있고 두 선이 겹치는 지점을 구하는 것은 plane sweeping으로 O(NlogN)에 할 수 있다. 이런 종류의 코드는 여기저기 신경 쓸 디테일이 많은데, 고치느라 시간을 어느 정도 쓰긴 했지만 생각보다 많이 쓰지는 않은 것 같아 다행이었다.

1번으로 다시 돌아와서 상수질(?)을 좀 더 한 결과 100점을 받긴 받을 수 있었다.

(*사실 내가 짠 게 정해가 아니라고 한다... 정해는 O(k^2NlogN)이라는데 그럴 거면 왜 k가 8인지 잘 모르겠다. 희망고문 비슷한 건가..)

3번은 트리가 하나 있고 각 노드에 0~9 사이의 번호를 매기는데, 특정한 5개의 연속한 노드(부모-자식 관계로 이어져 있다)에 들어올 수 "없는" 조합들이 M개 주어질 때 조건을 만족하지 못하는 조합의 갯수를 구하는 것이다. 약간 생각해 보면 각 노드별로 위에 달린 4개의 노드에 적힌 번호를 들고 다니면 "조건을 만족하는 조합의 가짓수"를 DP를 통해 구할 수 있다는 것을 알 수 있고, (전체 조합의 수, 즉 10^N에서 구한 DP값을 빼 주면 원래 문제에서 물어보는 답이 된다) N이 1000 이하일 때 이 DP가 시간 안에 돌아가게 된다.

그 다음으로 생각을 좀 더 해 본 결과 DP 과정에서 고려해 주어야 할 "의미있는 조합"이 O(M)개밖에 없다는 것을 알 수 있었다. (각 조건에 대해 해당하는 5개의 연속한 노드에만 고려할 조합이 추가되고 나머지 노드에는 전혀 영향을 미치지 않는다) 그것까지는 좋았으나 DP 상태를 어떻게 정의해야 상태 전이 등을 식으로 확실히 세울 수 있을지 고민하다가 너무 헷갈려서 결국 끝날 때까지 풀지 못 했다. "의미있는 조합"이라는 것이 ((아무거나), (아무거나), 5, 2)와 같이 어디까지는 상관이 없다가 밑에 몇 개만 결정이 되는 꼴로 나오고, 거기에다가 의미있는 조합에 해당하지 않는 "나머지" 조합까지 고려를 같이 해 주어야 돼서 생각하다가 꼬였다.


3번같이 "복잡한 생각"을 요구하는 문제를 고민하는 능력이 부족한 것 같은 느낌이 든다. 결국 대회장에서 이런 문제를 풀 수 있으려면 평소에 정말 많이 푸는 수 밖에 없겠다는 생각이 든다.

'알고리즘 > 국대 멘토교육' 카테고리의 다른 글

대회실습 5 (6.4)  (0) 2017.06.04
대회실습 4 (5.28)  (1) 2017.05.28
대회실습 2 (5.12)  (2) 2017.05.13
대회실습 1 (5.7)  (0) 2017.05.07
단층 풀이  (0) 2017.05.06