[C++] 26648번 물정수열

 

 

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

---

 

25/01/04

 

 

그리디적으로 생각하면 해결할 수 있는 문제다. 그리디적으로 접근하기 위한 한 가지 핵심적인 관찰이 필요하다.

---

 

문제 접근 방식:

 

 

한 가지 핵심적인 관찰을 해야한다.

 

우리는 결국 중앙값이 항상 증가하도록 세 과목 중 한 과목의 점수를 조작할 수 있다.(혹은 조작해야만 한다.)

 

기존 세 과목의 점수가 $a, b, c$라고 가정하자. 일반성을 잃지 않고, $a < b < c$라는 대소관계가 성립한다고 하자.

 

만약 $a$를 더 작게 조작한다고 해도 기존 중앙값 $b$에는 변함이 없다.

만약 $a$를 $b$보다 크거나 같고 $c$보다 작도록 조정한다면, 그 조정한 값이 중앙값이 된다.

만약 $a$를 $c$보다 크거나 같도록 조정한다면, $c$가 중앙값이 된다.

 

만약 $b$를 $a$보다 작도록 조정한다면 $a$가 중앙값이 될 것이다.

만약 $b$를 $a$보다 크거나 같고 $c$보다 작도록 조정한다면 $b$가 중앙값이 될 것이다.

만약 $b$를 $c$보다 크도록 조정한다면 $c$가 중앙값이 될 것이다.

 

마찬가지로 $c$도 범위를 조정해보면, 우리는 최종적으로 $a, b, c$ 셋 중 어느 것을 어떤 범위로 조정하던 간에 그 중앙값의 범위는 항상 $m$보다 크거나 같고 $M$보다 작거나 같다는 사실을 확인할 수 있다.(여기서 $m$은 세 값의 최솟값, $M$은 세 값의 최댓값을 의미한다.)

 

이를 이용하여 그리디적으로 생각해보자.

 

우리는 중앙값 수열이 항상 증가하기를 원하므로, 가능하다면 이전 중앙값과의 증가 차이가 항상 작기를 원한다.

 

따라서, 이전의 중앙값이 현재 $a, b, c$중 최댓값, 즉, $M$보다 크거나 같다면 우리는 현재 과목을 어떻게 골라서 어떻게 조정한다고 할 지라도 항상 중앙값이 $M$으로 밖에 나올 수 없으므로, 증가하는 중앙값 수열을 만들 수 없다.

 

만약 이전의 중앙값이 $m$보다 작거나 같고 $M$보다 크다면, 중앙값을 적당히 조절하여 이전의 중앙값보다 $1$크게끔 만들 수 있다.

 

만약 이전의 중앙값이 $m$보다 작다면 중앙값을 $m$으로 만들면 이전 중앙값과의 증가 차이가 가장 작다.

 

따라서, 이를 참고하여 구현하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 26648번 물정수열
// 그리디
/*
접근 방법:
최대한 점수를 낮출 수 있다면 이득이다.
중앙값은 우리가 조절할 수 있는데, 기존에 주어진 숫자가 a, b, c이고,
a가 min, c가 max라고 하면 a부터 c까지 중앙값을 조절할 수 있다.
그렇게 점수를 조절하다가 더이상 조절할 수 없다면 불가능을 하면 된다.
*/
#include <iostream>
#include <vector>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

int main(void){
    fastio;
    int N; cin >> N;
    vector<int> A, B, C;
    int a, b, c;
    for (int i = 0; i < N; i++){
        cin >> a;
        A.push_back(a);
    }
    for (int i = 0; i < N; i++){
        cin >> b;
        B.push_back(b);
    }
    for (int i = 0; i < N; i++){
        cin >> c;
        C.push_back(c);
    }
    int nxt = -1, m, M;
    for (int i = 0; i < N; i++){
        a = A[i], b = B[i], c = C[i];
        m = min(min(a, b), c), M = max(max(a, b), c);
        if (nxt >= M){
            cout << "NO";
            return 0;
        }
        else if (m <= nxt && nxt < M){
            nxt++;
        }
        else{
            nxt = m;
        }
    }
    cout << "YES";
    return 0;
}