문제 개요
세 개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. A[0] + A[2] = 2 × A[1]이 성립할 때, A[1]은 A[0]과 A[2]의 산술 평균이 됩니다. 이때 세 수의 산술 평균 편차는 다음과 같이 정의됩니다.
d(A[0], A[1], A[2]) = |A[0] + A[2] − 2 × A[1]|
우리는 다음 연산을 원하는 만큼 반복해서 수행할 수 있습니다. 인덱스 집합 {0, 1, 2}에서 서로 다른 두 인덱스 i와 j를 선택한 뒤, A[i]를 1 증가시키고 A[j]를 1 감소시킵니다. 이러한 연산을 통해 만들 수 있는 산술 평균 편차의 최솟값을 구하는 것이 목표입니다.
예를 들어 입력이 A = [2, 2, 6]이라면 출력은 1이 됩니다. A[0]을 1 감소시키고 A[1]을 1 증가시키면 배열은 [1, 3, 6]이 되며, 이때 편차는 |1 + 6 − 2 × 3| = 1이기 때문입니다.
접근 방법
이 문제의 핵심은 각 연산이 값 (A[0] + A[2] − 2 × A[1])에 미치는 영향을 분석하는 것입니다. 한 번의 연산을 수행하면 이 값은 1 또는 2만큼 증가하거나 감소합니다. 여기서 중요한 관찰은 다음과 같습니다.
- i = 0 또는 i = 2를 선택해 값을 증가시키면 편차 식의 값이 1 증가하고, j = 0 또는 j = 2를 선택하면 1 감소합니다.
- i = 1을 선택하면 −2 × A[1] 항 때문에 값이 2 감소하고, j = 1을 선택하면 2 증가합니다.
즉, 모든 연산은 이 값을 ±1 또는 ±2만큼 변화시킵니다. 모듈로 3의 관점에서 보면 ±1과 ±2는 동일한 잉여류에 속하므로, 어떤 연산을 수행하더라도 이 값을 3으로 나눈 나머지는 절대 변하지 않습니다. 반면, 연산을 반복하면 편차의 절댓값은 계속 줄일 수 있으므로 최종적으로 남는 최솟값은 나머지가 0일 때 0, 그렇지 않을 때 1이 됩니다.
풀이 단계
이 문제는 다음 단계로 해결할 수 있습니다.
a := A[0] b := A[1] c := A[2] return min(1, ((a + c - 2 * b) % 3 + 3) % 3)
C++에서 나머지 연산자(%)는 음수에 대해 음수 결과를 반환할 수 있으므로, ((x % 3) + 3) % 3 형태로 계산하면 항상 0 이상의 올바른 나머지를 얻을 수 있습니다.
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A)
{
int a = A[0];
int b = A[1];
int c = A[2];
return min(1, ((a + c - 2 * b) % 3 + 3) % 3);
}
int main()
{
vector<int> A = { 2, 2, 6 };
cout << solve(A) << endl;
}입력
{ 2, 2, 6 }출력
1
복잡도 분석
이 풀이는 배열의 세 요소를 한 번씩만 확인하면 되므로 시간 복잡도는 O(1)이며, 추가적인 공간도 사용하지 않으므로 공간 복잡도 역시 O(1)입니다. 연산 횟수와 무관하게 상수 시간에 답을 구할 수 있다는 점이 이 접근법의 가장 큰 장점입니다.