BOJ 19631 Wrong Answer
문제 내용
다음의 문제를 푸는 틀린 코드가 주어집니다.
1번부터 번까지 개의 스테이지를 가진 게임에서 2명의 플레이어블 캐릭터가 1번 스테이지에 있습니다. 한 명의 플레이어블 캐릭터를 스테이지 에서 스테이지 로 이동하는 데에 비용 가 듭니다.
1번을 제외한 모든 스테이지를 둘 중 정확히 하나의 캐릭터가 방문하도록 하는 데 드는 최소 비용을 구하세요.
이 코드가 출력하는 비용이 실제 최소 비용의 96배 이상이 되도록 하는 입력 파일을 출력하세요. (, )
문제 풀이
스포일러
먼저, 96배라는 차이를 달성하려면 실제 최단 경로는 매번 1을 따라가고 주어진 코드는 매번 100을 따라가야 할 것이라고 추측할 수 있습니다.
1에서 2로 가는 것은 모든 해에서 한 번은 거쳐야 하기 때문에, 비용을 1을 매깁니다.
그 다음으로 1에서 3으로 갈 수도 있고 2에서 3으로 갈 수도 있는데, 두 비용을 모두 1로 두면 (1, 3)과 (2, 3)의 두 개의 최적 상태가 만들어집니다. 주어진 코드는 (3, 2)로 갑니다. 주어진 코드에서는 sx와 sy의 대소관계가 중요하고 비대칭(sx + 다음 비용 == sy + 다음 비용이면 y의 이동을 선택)이기 때문에 현재 상태의 두 값의 순서를 바꾸면 안됩니다.
이제 다음 최적 경로를 (1, 3)에서 진행하는 것으로 두면 여기서부터 100:1의 비율을 만들어낼 수 있습니다.
- 1 -> 4를 1로 두고 2 -> 4와 3 -> 4를 모두 100으로 두면 최적은 (3, 4), 틀린 코드는 (3, 4)로 갑니다. 틀린 코드의 누적 비용(sx, sy)은 (1, 101)입니다.
- 누적 비용의 차이가 크기 때문에, 3 -> 5에 100을 주고 4 -> 5에 1을 줘도 틀린 코드는 (5, 4)로 가게 됩니다. 최적 코드는 (3, 5)로 갑니다. 누적 비용은 (101, 101)로 동일해집니다.
- 3 -> 6을 1로 두고 4 -> 6과 5 -> 6을 모두 100으로 두면 최적은 (5, 6), 틀린 코드는 (5, 6)으로 가게 됩니다. 누적 비용은 (101, 201)입니다.
- ...
여기서 반복 패턴이 발생하므로 이대로 까지 연장하여 만들어지는 데이터를 출력하면 됩니다.