백준 14487 (욱제는 효도쟁이야!!) [Python/파이썬] [Greedy/그리디]

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

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

 

---

나:

n  =  int(input())
costs = list(map(int,input().split()))
print(sum(costs)-max(costs))

완성된 코드는 위와 같다.

코드 자체는 간단하지만 ' 둘째 줄에 i번째 마을과 i+1번째 마을의 이동비용 vi가 n개 주어진다. n번째 vi는 n번째 마을과 1번째 마을의 이동비용을 의미한다. ' 의 문장을 제대로 이해하는 것이 중요한 문제였다. 

첫째 줄에 마을 수 n 을 정수형태로 받는다.

두번 째 줄에는 n 만큼 마을의 '이동비용'을 받는다.

모든 마을을 관광하기 위한 '최소' 이동비용을 구하기 위해서는 가장많은 이동비용을 제외한 나머지의 합을 더하면 된다.

즉, 이동 비용이 많은 곳에서 관광을 시작하면 된다. 예제 1의 경우 두번째 마을 -> 세번 쨰 마을 일때 비용이 6으로 가장 많으니 세번째 마을 에서 출발해 한 바퀴 돌아서 두번 째 마을에 도착하게 되면 최소한의 비용으로 모든 마을을 관광하게 된다.

그래서 최종적으로 모든 비용의 합을 sum 을 통해 구하고 이들 중 가장 큰 값을 max 함수를 통해 뺀 값을 출력한다.