[백준(BOJ)] 15903번 : 카드 합체 놀이 - C++[CPP]

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

15903번: 카드 합체 놀이

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 우선순위 큐

 

---

 

⊙ 문제 접근 과정

 

결론부터 말하면 가장 작은 두 값을 더하고 두 장 모두에 덮어쓴 값이 최솟값이다.

 

4 2 3 1, 총 4장의 카드가 있다. 우선 크기 순으로 정렬해보자.

 

1 2 3 4

 

덮어썼을 때 가장 적게 값이 증가해야 한다. 그러려면 두 값 모두 작아야 한다.

한 장만 작고 한 장이 크다면 결국 큰 값이 덮어씌워져 최솟값이 되지 않는다.

 

따라서 매번 정렬하고 가장 작은 값 두개를 선택하여 덮어쓰는 것을 반복하면 된다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int N, M;
vector<ll> v;

int main() {
    cin >> N >> M;

    for(int i=0;i<N;i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }

    for(int i=0;i<M;i++) {
        sort(v.begin(),v.end());
        ll temp=v[0]+v[1];
        v[0]=temp; v[1]=temp;
    }

    ll total=0;

    for(int i=0;i<v.size();i++)
        total+=v[i];
    

    cout << total;
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!