[cpp 알고리즘] 백준 20300 서강근육맨

[백준] 20300 서강근육맨 cpp 풀이

알고리즘: 그리디 알고리즘, 정렬

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

 

문제 요약

- 헬스장에 있는 N개의 운동기구 중에 하루에 2개의 운동기구로 운동한다. 홀수 개의 운동기구가 있는 경우에는 마지막 PT를 받을 때는 운동 기구를 하나만 사용한다.

- 이 때 운동기구마다 근손실이 일어나는 정도가 다르다. PT를 한 번 받을 때의 근손실 정도가 M을 넘지 않도록 하고 싶다. 이때, M의 최솟값을 구하는 문제이다. (운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.)

풀이 정리

(1) 입력받은 근손실 정도를 (오름차순으로) 정렬한다. 

(2-1) 운동기구 개수 N이 홀수인 경우에는, 근손실 정도가 최댓값인 운동 기구를 빼 둔다. -> 2-2로 이동

(2-2) N이 짝수이므로, 가장 큰 값과 가장 작은 값의 합을 구해 근손실 정도를 구한다.

(3) 근손실 정도의 최댓값을 구한다.

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

int N;
vector<ll> v;

int main(){
    
    cin >> N;
    for(int i=0; i<N; i++){
        ll input; cin >> input;
        v.push_back(input);
    }
    
    sort(v.begin(), v.end());
    
    ll ans = -1;
    
    if(N%2==1){ //홀수일 때
        ans = v.back();
        v.pop_back(); //뒤에 있는게 정말 삭제되는 게 아니라 마지막 인덱스가 줄어드는 것
    }
    
    // 짝수 개 남았을 때
    int totalsize = v.size();
    for(int i=0; i<(totalsize-1)/2; i++){
        ll tmp = v[i] + v[totalsize-1-i];
        if(tmp > ans) ans = tmp;
    }
    
    cout << ans;
    return 0;
}

 

Vector(벡터) 에 대하여...

최대/최소의 합을 구하면 된다는 풀이를 구현하기는 쉬웠다... 하지만 벡터의 pop_back()에 대해서 오해하고 있었던 부분이 있었다. 

 

[문제상황]

- 첫 코드를 작성할 때 v.size()를 이용하지 않고, 직접 N값을 이용했었다.

    => V[N-1]의 값이 pop되어서 없을 줄 알았는데, 이 값을 읽어오고 있었다. 

- vector에서 마지막 최대 값을 pop_back() 하면 v의 size는 줄어든다. 하지만 v[최대 index]로 했을 때는 그 값이 여전히 유효했다. 

 

[vector pop원리]

- 마지막 요소를 소멸시킨 다음, 벡터의 크기를 1 줄이는 방식이다.

=> 벡터의 크기는 줄어들지만, 요소를 물리적으로 메모리에서 삭제하지는 않는다.

=> 벡터의 논리적인 크기만 줄어들고, 실제 메모리는 그대로 남아있다.

 

- 소멸자 호출: pop_back이 호출되면, 벡터의 마지막 요소의 소멸자가 호출되어 그 객체가 가지고 있는 자원(예: 동적 할당 메모리, 파일 핸들 등)을 해제한다. 하지만, 메모리 자체는 해제되지 않고 여전히 벡터의 내부 배열에 남아 있다.

- 크기 감소: 벡터의 크기를 나타내는 멤버 변수가 1 줄어든다. 벡터의 크기(size)는 줄어들지만, 벡터의 용량(capacity)는 변하지 않는다.

 

기타

백준 20300 풀이