백준 20300 C++

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

20300번: 서강근육맨

 

문제 정리

근손실 미친놈

근손실 정도 = 입력받은 두 근손실 정도 벡터(또는 배열) 2개의 합

합의 max값이 가장 적게 되는 max(==M)을 구해라!

 

생각

모든 경우의 수를 전부 구해서 가장 작은 M값을 구하면 될 것 같은데...

중요한 건  두 개를 고르는 경우를 조합으로 구해야 중복도 안나고! 좋을 듯

전에 썼던 조합으로 푸는 dfs를 사용하면 될 것 같다!

근데 이렇게 어려운 문제가 아니었나보다... 그냥 정렬을 해서 처음 값과 끝 값을 더한게 M값이 되면 된다네?? 아놔... 

문제 이해실력 꽝~~~,,,

 

정렬로 푸는 방법

1. 들어오는 값이 홀수일 때와 짝수일 때를 나누고

2. 정렬을 해서 M을 구한다

 - 홀수일 때 : 가장 큰 값(하루에 그 것만 한 번 하게 둠)과그 다음으로 큰 값 + 가장 작은 값을 비교해서 작은 값을 M으로 설정한다

 - 짝수일 때 : 처음과 끝 값을 더하고 이걸 M으로 설정한다

 

코드 (틀린 버전)

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

int main() {
    int n, m;
    vector<int> v;
    cin >> n;

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

    sort(v.begin(), v.end());

    if(n%2 != 0){
        int temp1 = v.back();
        int temp2 = v[0]+v[v.size()-2];
        m = max(temp1, temp2);
    }
    else{
        m = accumulate(v.begin(), v.end(),0);
    }

    cout << m;
}

하 틀린게 분명 없는데... 뭘까

혹시... m을 계속 갱신해야 하나??????? 하 그런가

약간 문제 이해가 덜 된 것 같기도 하고 ㅎ

int temp3 = v[0] + temp1;
m = max(temp1, max(temp2, temp3));

홀수일 때 경우의 수가 부족한 건 아닐까 이렇게 temp3을 추가도 해봤지만 다 틀렸대 ㅗㅗㅗ

 

결국 빠른 이해를 위해 인터넷을 찾아봤고...

역시나 내 문제 이해가 잘못됐다는걸 깨달았다

최대 최소 값을 더한 값과 마지막 값을 비교해야한다!

 

아니 근데 수정해도 이상하게 안 되는데... 한참 삽질하다가 문제점 발견

long long으로 받아야함!!!! ㅗㅗㅗㅗㅗ

암튼 정답 코드

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

int main() {
    int n;
    cin >> n;
    vector<long long> v(n);

    for(int i=0 ; i<n ; i++){
        cin >> v[i];
    }

    sort(v.begin(), v.end());

    long long m = 0;
    if(n%2 != 0){ // 홀수
        m = v.back();
        for(int i=0 ; i<n/2 ; i++){
            m = max(m, v[i] + v[n - i - 2]);
        }
    }
    else{ // 짝수
        for(int i=0 ; i<n/2 ; i++){
            m = max(m, v[i] + v[n - i - 1]);
        }
    }
    cout << m;
}

문제를 잘 읽자...

아무리 해도 안되면 나를 의심하지 말고 변수형을 의심해보자... ㅠㅠㅠㅠ

 

알게된 점

벡터의 요소의 합 구하는 방법 - accumulate를 사용

#include <numeric>

sum = accumulate(v.begin(), v.end(), 0);
// 더하고자 하는 두 값과 초기값(대부분0)을 넣어준다