백준14487 욱제는 효도쟁이야!!

작성일 | In

문제 링크

  • http://icpc.me/14487

문제 출처

  • 2017 선린 봄맞이 대회 A번

시간복잡도

  • O(n)

풀이

한 쪽 방향으로만 도는 것이 최소 비용이 되는 것은 자명한 사실입니다.
모든 마을을 방문하면서 최소 비용이 들게 하기 위해서는 가장 비용이 큰 도로만 지나지 않으면 됩니다.
그러므로 모든 수를 다 더한 뒤, 최댓값만 빼주면 해를 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int maxi = 0;
    long long ans = 0;
    int n; cin >> n;
    for(int i=0; i<n; i++){
        int t; cin >> t;
        maxi = max(maxi, t);
        ans += t;
    }
    ans -= maxi;
    cout << ans;
}