문제 설명
N개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. N개의 상자가 하나의 원을 이루며 배치되어 있고, i번째 상자에는 A[i]개의 돌이 들어 있습니다. 우리는 다음 연산을 반복 수행하여 모든 상자에서 돌을 완전히 비울 수 있는지 확인해야 합니다.
- 임의의 상자 i를 하나 선택합니다.
- j가 1부터 N까지 변하는 동안, (i+j)번째 상자에서 정확히 j개의 돌을 제거합니다. 이때 (N+k)번째 상자는 k번째 상자와 동일하게 취급합니다(원형 순환).
- 만약 어떤 상자에 충분한 돌이 들어 있지 않다면 해당 연산은 수행할 수 없습니다.
예를 들어 입력이 A = [4, 5, 1, 2, 3]이라면 출력은 True가 됩니다. 두 번째 상자에서 시작하면 모든 돌을 제거할 수 있기 때문입니다.
해결 접근 방법
이 문제는 수학적 성질을 활용하면 효율적으로 해결할 수 있습니다.
연산을 한 번 수행할 때마다 1 + 2 + … + N = N(N+1)/2개의 돌이 제거됩니다. 따라서 전체 돌의 개수는 반드시 p = N(N+1)/2로 나누어떨어져야 하며, 그 몫 k는 연산을 수행해야 하는 횟수가 됩니다.
그다음에는 인접한 상자들 사이의 돌 개수 차이를 이용해 추가 조건을 검증합니다. 모든 차이 값의 합이 0이어야 하고, 각 상자에 대해 (차이 + k)가 N으로 나누어떨어지면서 동시에 음수가 아니어야 합니다. 이 조건들을 모두 통과하면 모든 돌을 제거하는 것이 가능합니다.
단계별 과정을 정리하면 다음과 같습니다.
- n을 배열 A의 크기로 설정합니다.
- 크기가 (n+1)인 배열 a와 b를 선언합니다.
- sum := 0, p := n * (n + 1) / 2로 초기화합니다.
- i가 1부터 n까지 증가하는 동안 a[i] := A[i-1]을 대입하고 sum에 누적합니다.
- sum을 p로 나눈 나머지가 0이 아니라면 false를 반환합니다.
- k := sum / p로 설정합니다.
- i가 1부터 n까지 증가하는 동안 b[i] := a[i] - a[(i mod n) + 1]을 계산합니다.
- 배열 b의 값을 다시 a에 옮겨 담으면서 합을 구하고, 그 합이 0이 아니면 false를 반환합니다.
- 모든 i에 대해 (a[i] + k)가 n으로 나누어떨어지지 않거나 a[i] + k가 음수라면 false를 반환합니다.
- 위 조건을 모두 통과하면 true를 반환합니다.
예제 코드
아래 C++ 구현을 통해 좀 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A) {
int n = A.size();
vector<int> a(n + 1);
vector<int> b(n + 1);
int sum = 0, p = n * (n + 1) / 2;
for (int i = 1; i <= n; i++) {
a[i] = A[i - 1];
sum += a[i];
}
if (sum % p != 0) {
return false;
}
int k = sum / p;
for (int i = 1; i <= n; i++) {
b[i] = a[i] - a[i % n + 1];
}
sum = 0;
for (int i = 1; i <= n; i++) {
a[i] = b[i];
sum += a[i];
}
if (sum != 0) {
return false;
}
for (int i = 1; i <= n; i++) {
if ((a[i] + k) % n != 0 || a[i] + k < 0) {
return false;
}
}
return true;
}
int main(){
vector<int> A = { 4, 5, 1, 2, 3 };
cout << solve(A) << endl;
}입력
{ 4, 5, 1, 2, 3 }
출력
1
출력값 1은 true를 의미합니다. 즉, 두 번째 상자에서 시작해 연산을 반복하면 모든 상자의 돌을 성공적으로 제거할 수 있다는 뜻입니다.