[백준]평균값 수열(5485)

문제 링크 : [백준]평균값 수열(5485)

5485번: 평균값 수열

 

문제 설명

A₁, A₂, A₃...의 수열이 주어집니다.

이 수열은 차례로 (X₁ + X₂) / 2, (X₂ + X₃) / 2, (X₃ + X₄) /2 를 의미하는 수입니다.

X₁, X₂...가 순서대로 비내림차순으로 이루어진다고 할 때, 가능한 수열의 경우의 수를 구하세요.

입력

N(원소의 갯수, 2 <= N <= 5,000,000)

A_i(평균의 값, 0 <= A_i <= 1,000,000,000)

3
2
5
9

 

출력

4

 

카테고리

#수학

 

시간 복잡도 상한

O(N)

 

해결 방법

1. 먼저 맨 앞의 숫자가 결정되면 이후의 숫자들은 한번에 구해진 다는 것을 확인합니다.
   1. 예제에서 첫번째 수가 1로 정해진다면, {1, 3, 7, 11} 하나의 경우밖에 없습니다.
2. 그리고 원래 수열이 비내림차순이어야 되기 때문에, 두 번째로 올 수 있는 수 X₂는 A₁ <= X₂ <=A₂까지의 범위를 가집니다.
   1. X₂가 A₁보다 작은 경우, 평균을 맞추려면 X₁이 X₂보다 커야합니다.
   2. X2가 A₂보다 큰 경우도 마찬가지로 X₂가 X₃보다 커지게 됩니다.
3. X₃의 범위는 A₃ * 2 - A₂ <= X₃ <= A₃ * 2 - A₁가 됩니다.(2와 같은 이유입니다.)
4. 그러나 조심해야 할 것은, 3번에서 구한 범위 중, 내림차순의 경우가 발생 할 수 있습니다.
5. 역순이 발생하는 경우는 상한의 범위가 평균을 초과할 때 발생합니다.
   1. 3에서 보면 A₃ * 2 - A₁이 A₃보다 큰 경우입니다.
6. 이런 경우, A₃을 상한으로 보정해주면 됩니다.
7. 처음에 쉽게 생각하고 풀었을 때 틀렸던 테스트케이스는 아래와 같습니다.

7
2
5
7
8
9
12
14
15
 
정답 : 1

시간복잡도

O(N)

코드

#include<iostream>
using namespace std;
int n,x,y,i,s,a,b;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>x>>y;
    a=y;b=y*2-x;
    for(i=2;i<n;i++){
        x=y;
        cin>>y;
        a=2*y-a;
        b=max(2*y-b,y);
        swap(a,b);
    }
    cout<<max(b-a+1,0);
}