[2020 Goricon] BOJ 20116 상자의 균형

문제 링크 : www.acmicpc.net/problem/20116

20116번: 상자의 균형

누적합 등으로 쌓여 있는 상자들의 평균 중심을 구해가며 안정적인 구조인지 판단하면 된다.

이 풀이에서는 맨 위 상자부터 계산하였다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
 
using namespace std;
typedef pair<int, int> p;
 
int n, l;
int mids[200000];
 
void init() {
    int input;
    cin >> n >> l;
 
    for (int i = 0; i < n; i++) {
        cin >> input;
        mids[i] = input;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    double mean;
 
    init();
    
    //최초 좌우
    mean = (double)mids[n - 1];
    int cnt = 1;
 
    for (int i = n - 2; i >= 0; i--) {
        //바로 위의 상자와 맞는지 확인 (아예 떨어진 경우)
        if (mids[i] > mids[i + 1] + l || mids[i] < mids[i + 1] - l) {
            printf("unstable\n");
            return 0;
        }
        //현재 상자 위의 모든 상자에 대해 맞는지 확인
        if (mean >= mids[i] + l || mean <= mids[i] - l) {
            printf("unstable\n");
            return 0;
        }
        mean = (mean * cnt + mids[i]) / (cnt + 1);
        cnt++;
    }
 
    printf("stable\n");
 
    return 0;
}