[C++] 백준 22945 - 팀 빌딩

문제 이해 단계

---

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

22945번: 팀 빌딩

능력치가 다 다른 N명이 입력으로 들어온다.

이 중에서 2명을 뽑아서 값을 만들 때,
값을 구하는 공식은 아래와 같다.

 

(A와 B 사이에 존재하는 다른 사람 수)*min(A, B)


이러한 조건일 때 나올 수 있는 값의 최대치를 구하는 문제

 

 

문제 접근 단계

---

문제풀이를 위해 조건부터 살펴보자.


들어올 수 있는 사람 N은 최대 100,000까지 가능하고, 
능력치는 10,000까지 가능하다.

 

해당 계산에서는 사이에 있는 사람과 곱셈이 가능하기 때문에,
나올 수 있는 최대는 100,000 * 10,000 = 10^9
로 Int 자료형을 넘지 않는다.

 

 

 

2명을 고르는 것

해당 문제에서는 2명을 골라 계산을 하라고 했다.

 

만약 2명을 골라 계산하는 것을 일일이 한다면
N*N = 100,000 * 100,000 = 10^10으로 시간초과가 난다.

 

그래서 문제에서 대놓고 주는 건지는 모르겠지만,
선택된 두 사람 사이에 있는 사람들도
계산에 딱 2명만 쓰인다.

 

그래서 나는 투포인터가 생각이 났다.

 

중요한 것은 최댓값을 구하는 것이니까,
가장 큰 것부터 비교를 시작해서
최대한 값이 커지는 경우로 포인터를 옮긴다.

 

양 끝에서 포인터를 시작한다.

 

위와 같이 포인터를 양쪽 끝에서 시작한다.

 

우리가 구해야 하는 것은 최댓값이다.


여기서 두 포인터 중 하나를 옮겨야 할 때,
둘 중 계산 값이 더 커지기 위해서는
min(A, B) 값이 커져야 하기 때문에 1을 옮기는 것이 맞다.

더 작은 값인 왼쪽 포인터를 옮김

 

똑같은 논리로 이번에는
6보다 작은 5인 오른쪽 포인터를 옮긴다.

이번에는 오른쪽 포인터를 옮김

 

그러다가 왼쪽 포인터와 오른쪽 포인터가 연속되게 되면
계산 값이 0이 되므로 계산을 종료한다.

더 이상 값이 존재하지 않는다.

 

해당 과정에서 계산되는 값 중
최댓값을 찾으면 답이 된다.

 

이 과정을 코드로 구현하면 된다.

 

이제 문제 구현 단계에서 문제를 구현해 보자.

 

 

문제 구현 단계

---

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

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> v(N); // 개발자를 담는 배열
    for(int i = 0; i < N; i++) cin >> v[i];

    //각 포인터를 양 끝으로 위치시킴
    int left = 0, right = v.size()-1;

    int cnt = 0;
    // 두 포인터가 연속되면 종료
    while(left < right){
        int distance = right-left-1; // 두 포인터간의 거리
        int power = min(v[right],v[left]); // min 값
        cnt = max(cnt,distance*power); // 계산 최댓값(답)

        // 둘 중 작은 포인터를 왼쪽 또는 오른쪽으로 옮김
        if(v[right] > v[left]) left++; 
        else right--;
    }
    cout << cnt;

}

코드는 위에 설명한 게 전부여서
주석으로 전부 설명이 될 것이라고 생각한다.


설명은 여기까지이고 그림이 도움이 됐길 바란다.

 

 

 

시행착오

---

처음에는 DP인가 했다가,
아무리 봐도 값이 계속 바뀌길래 포기했다.


그러다가 굳이 개발자를 2명 고르길래,
불현듯 투포인터가 생각났다.

 

투 포인터를 하다가 포인터를 이래저래 배치해 보다가,
그냥 양 끝에 위치해 보니까 시간복잡도가 O(N)이 나오더라

 

코드는 정말 쉽게 짰다.
오랜만에 1시간 안에 풀어서 기분이 좋다.

 

 

 

 

생활비..

https://toss.me/howudong

howudong님에게 보내주세요