[그리디 알고리즘 Lv. 02] 11487번 욱제는 효도쟁이야!!

 

1. 문제
    욱제는 효도쟁이야!! (링크 참고)

    https://www.acmicpc.net/problem/14487

14487번: 욱제는 효도쟁이야!!

 

욱제는 KOI를 망친 기념으로 부모님과 함께 코드게이트 섬으로 여행을 떠났다. 코드게이트 섬에는 오징어로 유명한 준오마을(심술쟁이 해커 임준오 아님), 밥으로 유명한 재훈마을, 영중마을 등 많은 관광지들이 있다. 욱제는 부모님을 모시고 코드게이트 섬을 관광하려고 한다.

코드게이트 섬은 해안가를 따라 원형으로 마을들이 위치해있다. 임의의 A마을에서 임의의 B마을로 가기 위해서는 왼쪽 또는 오른쪽 도로를 통해 해안가를 따라 섬을 돌아야 한다. 섬을 빙빙 도는 원형의 길 외에 다른 길은 존재하지 않는다.

각 마을에서 마을까지의 이동비용이 주어질 때, 욱제가 최소한의 이동비용으로 부모님을 모시고 섬의 모든 마을을 관광하려면 얼마의 이동비용을 준비해야하는지 알려주자.

 

출처 : 백준 https://www.acmicpc.net/problem/14487

 

 

2. 문제 포인트

• 출발 마을은 선택 가능
• 마을에서 이동은 좌우 근접 마을만 이동가능
• 모든 마을 한번씩 방문

 

3. 접근법

• 최대 비용인 마을에서 시작한다!

• 위의 표를 보면 가장 비싼 구간인 D - C 구간을 피한 4번째 경로가 가장 작은 비용이 든다
• 코드상에서 계산시 가장 큰 비용을 빼고 나머지 비용을 더하면 간단하게 계산된다

 

반응형

 

 

4. 결과 코드

import sys

// 마을 개수는 문제 계산과 무관하다
vil_num = sys.stdin.readline()

// 구간별 요금을 리스트로 입력받는다
fee = list(map(int, sys.stdin.readline().split()))

// 구간별 요금 총 합에서 가장 요금이 큰 구간의 요금을 빼면 최소 이동 비용이 나온다
result = sum(fee) - max(fee)

print(result)