[Python] 백준 14487번_욱제는 효도쟁이야!!

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

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

 

• 욱제는 부모님을 모시고 코드게이트 섬을 관광하려고 함
• 코드게이트 섬은 해안가를 따라 원형으로 마을들이 위치해있음
• 임의의 A마을에서 임의의 B마을로 가기 위해서는 왼쪽 또는 오른쪽 도로를 통해 해안가를 따라 섬을 돌아야 함
• 섬을 빙빙 도는 원형의 길 외에 다른 길은 존재하지 않음
• 각 마을에서 마을까지의 이동비용이 주어질 때, 욱제가 최소한의 이동비용으로 부모님을 모시고 섬의 모든 마을을 관광하려면 얼마의 이동비용을 준비해야하는지 구하기

 

• 입력
  • 첫째 줄에 마을의 수 n이 주어짐 (1 ≤ n ≤ 50,000)
  • 둘째 줄에 i번째 마을과 i+1번째 마을의 이동비용 vi가 n개 주어짐
  • n번째 vi는 n번째 마을과 1번째 마을의 이동비용을 의미 (1 ≤ vi ≤ 1,000)
• 출력
  • 모든 마을을 관광하기 위해 필요한 최소 이동비용을 출력
• 시간 제한: 2초
• 메모리 제한: 512 MB

 

"""
입출력 예시)

(예제 입력 1) 
5
1 6 5 2 4
        -> 12

(예제 입력 2)
4
100 100 100 101
        -> 300
"""

 

 

## 의사코드 ##

# 모든 마을을 관광하기 위한 최소 이동비용
# 마을은 원형으로 위치

# vi(이동비용)가 가장 큰 경로의 i+1번째 마을부터 출발 
# 최소 이동비용 => 전체 비용의 합 - 가장 큰 vi값

 

# n = 5
# 1 6 5 2 4

# v1 = 1 (1 -> 2)
# v2 = 6 (2 -> 3)
# v3 = 5 (3 -> 4)
# v4 = 2 (4 -> 5)
# v5 = 4 (5 -> 1)

• 3번 -> 4번 -> 5번 -> 1번 -> 2번
  • 5 + 2 + 4 + 1
  • => 12

 

 

 

통과한 코드

n = int(input())
cost = list(map(int, input().split()))

# 최소 이동비용 = 전체 이동비용의 합 - 가장 큰 이동비용
print(sum(cost) - max(cost))

-> 최소 이동비용을 구하기 위해 vi(이동비용)이 가장 큰 경로의 i+1번째 마을부터 출발

=> 전체 이동비용의 합에서 가장 큰 vi 값을 빼면 됨

 

 

 

 

 

참고)

 

https://hostramus.tistory.com/138

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