BOJ 5485 - 평균값 수열 링크
(2024.04.22 기준 G2)

문제

길이 $n$의 감소하지 않는 평균값 수열 $m_1$, $\dots$, $m_n$이 주어질 때, 해당 수열을 평균값 수열로 가지는 수열 $s1$, $\dots$, $s_{n+1}$의 개수 출력

알고리즘

메모리 제한에 유의해야 하는, 애드혹 문제

풀이

$s_i$는 $[m_{i-1}, m_i]$ 범위에 있어야 하는 것은 직관적으로 알 수 있다. 그리고 $m_i$는 $s_i$와 $s_{i+1}$의 평균값이다. 그러면 $[m_{i-1}, m_i]$ 범위와 $[m_i, m_{i+1}]$ 범위에서 하나씩 수를 선택해서, 평균을 $m_i$로 만들 수 있어야 한다.

한 범위에서 $m_i$와의 거리가 $d$인 수를 선택했다면, 나머지 한 범위에서도 $m_i$와의 거리가 $d$인 수를 선택해야 한다. 이는 즉, 두 범위에서 선택하는 두 수가 $m_i$와의 거리가 같아야 하므로 범위가 서로 영향을 주게 된다. 구체적으로는, 앞의 범위의 최소가 뒤의 범위의 최대에 영향을 주고, 앞의 범위의 최대가 뒤의 범위의 최소에 영향을 준다.

$n$과 $m_i$의 범위가 매우 커서 모두 담아놓고 진행하면 메모리 제한에서 걸리기 때문에, $m_i$를 받을 때마다, 직전 범위와 비교하면서 범위를 다시 구하는 식으로 좁혀가면 된다.

단, 범위의 넓이가 $0$이 될 수도 있다. 이를 유의해서 풀어내면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;

    // 가능한 수의 범위를 줄여 나간다.
    int a, b, mn, mx;
    cin >> a >> b;
    mn = a; mx = b;
    for (int i = 2; i < n; i++){
        a = b;
        cin >> b;

        if (a * 2 - mx > b){
            cout << 0;
            return 0;
        }
        swap(mn, mx);
        mn = a * 2 - mn;
        mx = min(b, a * 2 - mx);
    }

    cout << mx - mn + 1;
}

• Python

import sys; input = sys.stdin.readline

n = int(input())

# 가능한 수의 범위를 줄여 나간다.
a = mn = int(input())
b = mx = int(input())
for _ in range(n - 2):
    a = b
    b = int(input())

    if a * 2 - mx > b:
        print(0)
        exit()
    mn, mx = a * 2 - mx, min(b, a * 2 - mn)

print(mx - mn + 1)