PS 이야기

문제에서 주어진 식을 그래프 DAG(Directed Acyclic Graph)로 잘 만들어주면, 비교적 쉽게 풀리는 문제다. 한 마디로, 이 문제를 노가다성 문제라고 생각한다. DAG를 구성하는 방법은 구체적으로 설명하지 않겠다. 까다로울 수 있지만 특별한 알고리즘이 필요한 것도 아니고 사람마다 저마다의 방법이 있을 것이라 생각하기 때문이다. 필자는 A(B|CD(E|_)G)E 가 입력으로 들어오면 아래와 같이 그래프를 구성했다. 그래프를 구성 한 뒤에는 DP(Dynamic Programming)을 통해 해결하면 된다.그래프를 구성하는 노드의 개수를 $N$이라 하고, 입력으로 주어지는 두 번째 문자열의 길이를 $L$이라 하자.우선 그래프에서 위상정렬를 통해 각 노드의 순서를 구한 뒤 그 순서대로 처리한다...

따로 설명할 것 없이, 문제에서 주어진 조건대로 해결 하면 된다.한 사람의 등수를 계산하는 것이기 때문에 따로 정렬해줄 필요도 없다. 문제 설명에 따라, 같은 시간에 이뤄진 제출이 없으므로, 같은 등수를 갖는 두 팀은 나올 수 가 없다. 문제 이름은 KCPC지만, 등수를 배정하는 기준은 2013년도부터 시행된 KOI 기준과 동일하다.

이 문제는 말리면 꽤 시간이 많이 걸릴 듯 해보이는 문제다.대회 당시에는 나는 문제도 모른채, 팀원이 막힘 없이 풀어주었다. 대회가 끝나고 글을 쓰기 위해 문제를 생각해보았는데, 생각하는데 오래 걸린 편이었다. 이런 개미 문제 컨셉은 BOI? CEOI? 기출 문제에도 있다. 그 문제에서 중요한 점은 "개미의 충돌이 있어도 개미가 떨어지는 시점(시간)은 변함 없다." 이다. 이 문제에서도 꼭 필요한 아이디어다.추가 설명을 하자면, 개미의 충돌이 있고 두 개미가 서로 방향을 바꿔, 왔던 길을 다시 가더라도 멀리서 봤을 때, 충돌 없이 개미가 서로 지나쳐 가는 것이랑 다를 것이 없다. 하지만 이 문제에서는 떨어지는 개미의 index를 알아야 한다.필자는 이 문제를 쉽게 생각했다가 말려 시간이 오래걸린 케이스다..