[C++ 풀이] 14487번. 욱제는 효도쟁이야!!

문제 분석

마을의 수가 주어지고, 한쪽으로만 마을을 쭉 도는 방법으로 모든 마을들을 가야한다. 

이때 최소한의 이동비용을 갖는 비용을 구하려면, 가장 이동비용이 높은 이동거리 하나만을 제외하면 된다. 

 

알고리즘 설계

벡터와 알고리즘 헤더의 sort()함수를 이용해서 구현했다.

벡터로 이동비용을 입력받아 넣고, sort함수로 오름차순으로 벡터를 정리한 후에

마지막 요소(가장 긴 이동비용)을 제외한 나머지를 다 더해주어 출력했다.

 

시간 복잡도

벡터에 이동비용 입력받기 - n

sum구하기 - n 

-> 대략 n+n = 2n 이므로 O(n) 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
1.마을수를 입력받음
2.이동비용을 입력받는다
3.최소 이동비용을 구한다
4.최소 이동비용을 출력한다
*/

int main() {
    //1
    int n;
    cin >> n;

    //2
    vector <int> move(n);
    for (int i = 0; i < n; i++) {
        cin >> move[i];
    }

    //3
    sort(move.begin(), move.end());
    
    //4
    int sum = 0;
    for (int j = 0; j < n - 1; j++) {
        sum += move[j];
    }
    cout << sum << '\n';

    return 0;
}

 

느낀 점

문제 그림을 보고 원형큐를 만들어서 풀어야하나? 싶었는데

굳이 어렵게 생각하지 않고, 가장 이동비용이 긴 하나만 제외하면 되는 문제였다.

쉽게 풀 수 있는 문제인데 헤맸던 것 같다 ㅠㅠ