플로이드 와샬2 백준 1613 c++ "역사" -[PlusUltraCode] https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net [필자 사고] 플로이드 와샬 알고리즘을 이용하면 쉽게 해결할 수 있는 문제이다. 입력창을 보면 선후 관계 화살표로 주어 졌으므로 와샬 알고리즘을 사용후에는 후속 조취가 필요하다. 그 이유는 다음과 같다. 1->4 의 값이 자연수이고 4->1의 값이 무한대일때 1과4는 선후관계가 형성 되었따. 1->4를 보면 선후관계를 알 수 있지만 4->1을 보면 선후관계를 판별할 수 없기 때문이다. 이 .. 2024. 2. 28. 백준 10159 c++ "저울" -[PlusUltraCode] https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net [필자 사고 ] 전형적인 플로이드 와샬을 이용하면 쉽게 해결할 수 있는 문제이다. 다만 알고리즘을 적용만 하면 답이 나오는 것이 아닌 이 문제의 특이한점은 순위가 결정 됬냐 안됬냐 하는 점이다. 만약 1->4 의 값이 자연수이고 4->1의 값은 무한대라고 했을 때 1과 4의 관계는 순위가 정해졌다고 말할 수 있따. 다만 플로이드 와샬 알고리즘을 적용하면 저런 형태로 나온다.. 2024. 2. 28. 이전 1 다음