백준 20116 상자의 균형 Kotlin (누적 합)

문제 출처 : https://www.acmicpc.net/problem/20116

20116번: 상자의 균형

문제

진수에게는 총 n개의 상자가 있다. 모든 상자는 2L × 2L 크기의 정사각형 모양이고, 상자의 밀도는 균일하다.

진수는 이 상자들을 바닥에서부터 차곡차곡 쌓아올린다. 바닥은 y=0 이다.

이 상자들을 바닥에 가까이 있는 있는 상자부터 각각 1번, 2번, ..., n번 상자라고 보았을 때 i번 상자의 중심은 (xi, 2L×i - L) 이 되고, 이는 i번 상자 1개의 무게 중심과 같다.

위에서 상자의 밀도는 균일하다고 가정하였으므로, 상자 여러 개의 무게 중심을 구하면 각각의 상자들의 무게 중심을 평균 낸 값이 된다.

진수는 원하는 중심 좌표에 상자들을 쌓아올릴 때 무너지지 않고 균형을 이루는 지를 알고 싶다.

모든 1 ≤ i < n 에 대하여 i+1, i+2, ..., n 번 상자들의 무게 중심의 x좌표가 i번 상자의 구간 안에 포함되면 박스 전체가 균형을 이루게 된다. i번 상자의 구간는 xi-L과 xi+L 사이로 정의하며, xi-L, xi+L은 포함하지 않는다. 따라서 상자 모서리에 걸쳐 있는 경우는 균형을 이루지 않는 것으로 한다.

n개의 상자들의 중심 좌표가 주어지면, 해당 상자들이 균형을 이루는지 알아내보자.

입력

첫 번째 줄에는 상자의 개수 n (1 ≤ n ≤ 200,000) 과 상자의 사이즈 L (1 ≤ L ≤ 109) 이 주어진다.

두 번째 줄에는 진수가 원하는 각각의 상자들의 무게 중심 x좌표 x1, x2, ..., xn (-109 ≤ xi ≤ 109) 이 주어진다.

출력

첫 번째 줄에 해당 상자들이 균형을 이룬다면 "stable", 그렇지 않다면 "unstable" 을 출력한다.

알고리즘 분류

• 수학
• 누적 합
• 물리학

풀이

문제 이해가 잘 되지 않았었다.

예제 2번을 보면 1번 상자 위에 상자들이 다 1번 상자 범위 안에 들어와 있는데 뭐가 문제지? 생각했는데

문제를 다시 잘 읽어보면 중심과 무게 중심은 다르다. 즉 입력으로 주어진 중심들을 이용해 무게중심을 구해야 하는데,

수학적으로 3개 상자 중심이 각각 9,11,13이면 세 상자의 중심의 합을 상자의 개수로 나눈 값 (9+11+13)/3 == 11이 세 상자의 평균 무게중심이라고 한다. 아무튼 그렇다.

그래서 결론은 1번 상자 위의 3개의 상자의 평균 무게중심이 1번 상자의 범위 안에 있어야 하고,

2번 상자 위의 2개의 상자의 평균 무게중심이 2번 상자의 범위 안에 있어야 하고,

3번 상자 위의 1개의 상자의 무게중심이 3번 상자의 범위 안에 있어야 한다.

 

그렇다면 누적 합을 적용할 수 있다.

우선 입력으로 받은 상자의 중심 리스트는 평균 무게중심과 비교해야 하기 때문에 냅두고,

추가로 pSum 배열을 만들어 중심들의 누적 합을 구한다.

 

이후 1번 상자부터 n-2번 상자까지를 기준으로 잡고 i번 상자의 중심을 xi-l ~ xi+l이라 하면, 해당 상자 위에 있는 상자들의 평균 무게 중심이 xi-l ~ xi+l에 속해야 하는 것이다.

속하지 않는다면 바로 unstable로 종료하면 되고, 평균 무게 중심이 10.1이고 xi-l이 10인 경우 stable하지만, 평균 무게 중심을 정수형으로 한다면 10이 되어서 unstable로 나오기 때문에, 평균 무게 중심을 실수값으로 해야 하는 것에 유의하자. (정수형으로 해서 3번 틀렸다.)

 

코드

val br = System.`in`.bufferedReader()
//1<=n<=200000
//1<=L<=10^9
fun main() = with(System.out.bufferedWriter()){

    val (n,l) = br.readLine().split(' ').map{it.toInt()}
    val input = br.readLine().split(' ').map{it.toInt()}
    val pSum = DoubleArray(n)
    pSum[0] = input[0].toDouble()

    for(i in 1 until n){
        pSum[i] = pSum[i-1]+input[i]
    }

    for(i in 0 until n-1){
        if((pSum[n-1]-pSum[i])/(n-1-i) <= input[i]-l || (pSum[n-1]-pSum[i])/(n-1-i) >= input[i]+l){
            write("unstable")
            close()
            return
        }
    }
    write("stable")

    close()
}