테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 한 번 남았다 ======

===== 풀이 =====
  * 잘못된 알고리즘에 대한 저격 데이터를 생성하라는 문제. 입력값도 따로 없다
  * 문제에서 잘못 작성한 알고리즘은 [[ps:단일_출발지_최단_경로#벨만-포드 알고리즘]] 이다. 음수 사이클이 없다면, 루프를 N-1번 돌릴때까지는 업데이트가 있을수 있지만, 그 이후에는 더이상 업데이트가 되지 않아야 한다. 
  * 하지만 문제의 오류 코드에서는 N-2번 루프를 돌리고 추가로 한번 더 반복했으니까, 총 N-1번 루프를 돌려 놓고서 업데이트가 있으니 음수 사이클이 있다고 주장한다. N-1번까지 업데이트가 되는 음수사이클이 없는 그래프를 찾으면 되는데, 간단한 것은 N개의 노드가 일직선 형태로 연결된 그래프이다. 모든 엣지의 가중치를 -1로 두고 벨만포드 알고리즘을 돌리면 마지막 끝에 있는 노드까지의 거리는 루프를 한번 돌때마다 1씩 줄어들어서, 최종적으로 N-1이 될때까지 갱신된다. 그러므로 이런 그래프를 만들어서 출력하면 된다,
  * 주의할 점은, 지문에 주어진 알고리즘 설명에는 없지만 코드를 보면, 데이터에 등장하는 순서대로 엣지들을 저장해놓고, 매 루프마다 저 엣지 순서대로 처리한다. 이말은, 1->2, 2->3, 3->4, ..., N-1->N 와 같은 순서로 엣지들을 제공하면 이 모든 업데이트가 한번의 루프에 처리될수도 있다는 것이다. 이렇지 않고 N-1번의 루프동안 처리되도록 하려면, N-1->N, N-2->N-1, ..., 1->2와 같은식으로 역순으로 엣지 정보를 주는 것이다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 13317. 한 번 남았다".

- Problem link: https://www.acmicpc.net/problem/13317
- Solution link: http://www.teferi.net/ps/problems/boj/13317

Tags: [AdHoc]
"""

N = 50

def main():
    print(N, N - 1)
    for i in reversed(range(1, N)):
        print(i, i + 1, -1)

if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}