image.png

문제 파악

두 선수의 기록 시간이 동일하면서 최소 시간으로 운동 종목을 선택하는 문제이다. 종목을 선택하는 것을 간선으로 보는 것을 제외하고선, 그래프로 보는 사고가 생각나지 않아 해결하지 못했다.

문제 풀이

문제 풀이의 핵심은 이 전에 풀었던 문제인 어린이날 문제와 유사하다. 어린이날 문제는 간선을 선택으로 정점을 나머지로 보았는데, 이 문제는 정점을 두 선수의 기록 차이로 간선을 운동 종목의 선택으로 보았다. 또한 어린이날 문제에서는 가중치가 없어 다익스트라 알고리즘을 쓸 필요는 없었지만 이 문제의 경우 최소의 시간이라는 조건이 있기 때문에 다익스트라 알고리즘을 사용해야 하며 가중치는 A국선수 또는 B국선수의 예상 기록으로 본다.

이렇게 하면 정점들 사이의 관계가 설정되며 가중치를 따라 다익스트로 알고리즘을 통해 스패닝 트리를 만들 수 있다. 이 때 종목을 선택하는 데 중복을 허용하므로 모든 정점에서는 종목의 수 만큼의 간선을 가질 수 있게 된다. 이렇게 된다면 양의 무한대, 음의 무한대까지 발산하는 경우가 생길 수 있기 때문에 정점의 개수를 제한해 줘야한다.

정점의 개수는 -200부터 200까지 401개까지만 사용하면 된다. 이 범위는 한 종목의 두 선수 기록의 최대 차이이므로 반드시 있어야한다. 이 범위를 넘어서는 정점은 최소 기록을 따지는데 불필요하게 밖으로 벗어나는 경우이므로 생각하지 않아도 된다.

느낀점

그래프로 사고하는 방법. 어린이날 문제와 유사하게 문제에서 제시한 조건들을 통해 정점과 간선을 설정하는 것이 중요하다. 어린이날 문제도 그렇고 이 문제도 그렇고 어떤 선택을 하는 것이고 선택을 함에 따라 상태가 변화하며 만족시켜야 하는 조건을 변화의 끝에 둔다고 생각하면 좋을 것 같다.