반응형
SMALL
26646번 알프스 케이블카
-
26646번 알프스 케이블카알고리즘 2023. 2. 16. 10:59
문제 설명 이번 문제는 여러 산맥의 정상을 다른 산의 정상으로 잇는 와이어를 설치해서 이동할 경우, 노선의 설치 비용을 최소화하는 경우를 구하는 문제입니다. 와이어의 설치 비용 - 와이어 길이의 제곱 노선의 설치 비용 - 와이어의 설치 비용의 합 문제 풀이 아이디어 와이어 설치 비용의 최소값 위의 사진 예시를 보도록 하겠습니다. A-B-C를 잇는 경우와 A-C를 잇는 경우의 설치 비용을 비교해보면, A-B-C를 잇는 경우의 설치 비용은 66 A-C를 잇는 경우의 설치 비용은 122가 됩니다. 위에서 확인할 수 있듯이, 산 정상을 하나라도 건너 뛰어서 와이어를 잇게 된다면 설치 비용이 커짐을 알 수 있습니다. (모든 산은 직각 이등변 삼각형이므로 어떤 예시를 들게 되더라도, 정상 하나를 건너 뛰어서 와이어..