2019 CAL Season 1 #H 풀이

출제자 : 31기 이온조

정답 코드

#include <bits/stdc++.h>
using namespace std;
 
int A[1000009];
 
int main() {
    int N; scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d", &A[i]);
    int am1 = 0, am2 = 0, dm1 = 0, dm2 = 0;
    for(int i=1; i<=N; i++) {
        if(A[am1] <= A[i]) am2 = am1, am1 = i;
        else if(A[am2] <= A[i]) am2 = i;
        if(D[dm1] <= D[i]) dm2 = dm1, dm1 = i;
        else if(D[dm2] <= D[i]) dm2 = i;
    }
    if(am1 != dm1) printf("%d", A[am1] + D[dm1]);
    else printf("%d", max(A[am2] + D[dm1], A[am1] + D[dm2]));
    return 0;
}

 

풀이법

만약 공격력이 가장 높은 선수와 수비력이 가장 높은 선수가 다르다면, 그냥 두 선수를 뽑으면 된다.

문제가 되는 상황은 공격력이 가장 높은 선수와 수비력이 가장 높은 선수가 같을 때이다. 이 선수를 A라고 하자. A가 공격과 수비를 모두 할 수 없기 때문에, 다른 누군가를 뽑아야 한다. 그래서 A를 제외하고 공격력이 제일 높은 선수 B와 수비력이 제일 높은 선수 C를 뽑아서, (공격수, 수비수) 조합 중 (B, A)와 (A, C) 중 경기력이 더 좋은 팀을 뽑으면 된다.