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

 

설명에도 나와있다시피

prioriy queue를 사용을 권장한다

 

하지만 나는 우선 배열 후 정렬로 해보고 

안되면 우선순위 큐를 사용하려고 했다

배열을 순차대로 입력 받고

하위 두 값을 합하여 저장하는 방식으로 코드를 작성했다

 

이 과정에서 배열에 큰 값을 입력 받을 수 있도록

long long int 타입을 사용해야 했다

 

난 아직 백준의 이러한 부분이 낯설다

그래도 타입형에 대해 한 번 더 신경 쓸 수 있다는 점은 좋은 것 같다

// baekjoon 15903

#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>


using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}


int main(){
    init();
    
    int n, m;
    
    cin >> n >> m;
    
    long long int arr[n];
    
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    
    long long int temp;
    for(int i = 0; i < m; i++){
        sort(arr, arr + n);
        temp = arr[0];
        arr[0] += arr[1];
        arr[1] += temp;
    }
    
    long long int sum = 0;
    for(int i = 0; i < n; i++){
        sum += arr[i];
    }
    
    cout << sum;
    
}

생각보다 간단한 구조로 배열을 사용했을 때 해결할 수 있었다

다만 우선순위 큐로 작성한 결과들을 보았을 때 

시간이 0ms인 것을 보면

문제가 간단하지 않았다면 분명히 시간 초과가 떴을 것이다

나 또한 그걸 예상하고 있었지만 안 뜰 줄 몰랐다..

이후 우선순위 큐를 사용해서 다시 풀어볼 예정이다