반응형
2565
-
BOJ) 전깃줄 (2565 번)알고리즘/백준 2021. 1. 26. 19:18
전깃줄 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net A와 B 두 전봇대가 주어지고, 두 전봇대를 잇는 전기줄의 정보가 주어진다. 이 때, 전깃줄이 교차하는 경우를 없애기 위해 전깃줄을 제거해야 하는데, 가장 최소한의 전깃줄을 제거해서 교차하는 경우가 되게 만드는 문제다. 교차하는 가장 최소한의 전깃줄을 제거한다는 것은 전체 전깃줄에서 가장 올바르게 연결된 전깃줄 수를 빼주는 것과 성립한다. 전체 전깃줄 (n) - 가장 많이 올바르게 연결된 전깃줄 = 불필요하게 교차된 전깃줄의 최소값 여기서 가장 많이 올바르게 연..