C++로 블록 타워의 최소 추함(높이 차이) 구하기

문제 개요

n개의 원소를 가진 배열 A가 주어졌다고 가정해 보겠습니다. 일렬로 n개의 블록 타워가 세워져 있으며, i번째 타워의 높이는 A[i]입니다. 하루에 한 번씩 다음 연산을 수행할 수 있습니다. 서로 다른 두 인덱스 i와 j(i ≠ j)를 골라 타워 i에서 타워 j로 블록 하나를 옮기는 것인데, 이때 A[i]는 1 감소하고 A[j]는 1 증가합니다.

여기서 건물의 '추함(ugliness)'은 max(A) − min(A), 즉 가장 높은 타워와 가장 낮은 타워의 높이 차이로 정의됩니다. 목표는 위 연산을 자유롭게 반복했을 때 얻을 수 있는 최소 추함을 구하는 것입니다.

예제로 이해하기

입력이 A = [1, 2, 3, 1, 5]일 때 출력은 1입니다. 실제 과정을 살펴보면 다음과 같습니다.

1. i = 2, j = 0으로 세 번 연산 → 배열이 [2, 2, 2, 1, 5]로 변합니다.
2. i = 4, j = 3으로 한 번 연산 → [2, 2, 2, 2, 4]
3. i = 4, j = 2로 한 번 연산 → [2, 2, 3, 2, 3]

최종 배열에서 max(A) − min(A) = 3 − 2 = 1이므로, 더 이상 줄일 수 없는 최솟값 1에 도달하게 됩니다.

풀이 접근 방식

이 문제의 핵심은 아주 단순하지만 강력한 관찰 하나에 있습니다. 바로 블록을 옮기는 연산은 전체 높이의 합을 절대 변화시키지 않는다는 점입니다.

• 배열의 총합(sum)이 n으로 나누어떨어지는 경우: 모든 타워를 정확히 sum / n 높이로 맞출 수 있으므로 최소 추함은 0입니다.
• 총합이 n으로 나누어떨어지지 않는 경우: 모든 타워의 높이가 동일하다면 총합 역시 n의 배수여야 하므로 모순이 발생합니다. 따라서 적어도 두 타워 사이에는 높이 차이가 존재하며, 최소 추함은 1보다 작아질 수 없습니다. 반면 블록을 최대한 고르게 분배하면 추함 1은 항상 달성할 수 있습니다.

결론적으로 답은 "총합이 n으로 나누어떨어지는가?"라는 질문 하나로 결정되며, 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

알고리즘 단계

sum := 0
n := size of A
for i := 0 to n-1:
    sum := sum + A[i]
if sum mod n == 0:
    return 0
return 1

C++ 구현 예제

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

int solve(vector<int> A) {
    int sum = 0;
    int n = A.size();
    for (int i = 0; i < n; i++)
        sum += A[i];
    if (sum % n == 0)
        return 0;
    return 1;
}

int main() {
    vector<int> A = { 1, 2, 3, 1, 5 };
    cout << solve(A) << endl;
}

입력

{ 1, 2, 3, 1, 5 }

출력

1

마무리

겉보기에는 여러 번의 연산을 직접 시뮬레이션해야 할 것 같지만, 연산 후에도 변하지 않는 불변량(총합)에 주목하면 단 한 번의 나머지 연산으로 문제를 해결할 수 있습니다. 코딩 테스트에서 "반복적인 연산에도 유지되는 값"을 먼저 찾아보는 습관이 이런 유형의 문제를 빠르게 푸는 열쇠가 됩니다.