문제 개요
n개의 요소로 구성된 배열 A와 하나의 수 m이 주어졌다고 가정해 봅시다. 이때 배열의 요소들을 적절히 재배열하여 다음 수식을 만족할 수 있는지 확인해야 합니다.
$$\mathrm{\sum_{i=1}^{n} \sum_{j=i}^{n}\frac{A[j]}{j} = m}$$
여기서 A[j]/j 연산은 반올림이나 버림 없이 실수 나눗셈 그대로 계산됩니다.
예를 들어 입력이 A = [2, 5, 1], m = 8이라면 출력은 True입니다. 배열을 [1, 2, 5]로 배치하면 다음과 같이 계산되어 정확히 8이 되기 때문입니다.
(1/1 + 2/2 + 5/3) + (2/2 + 5/3) + (5/3) = 8
핵심 아이디어
겉보기에는 복잡해 보이는 이중 합 공식이지만, 자세히 살펴보면 간단한 규칙이 숨어 있습니다. 각 원소 A[j]는 안쪽 합에 정확히 j번 포함됩니다. 따라서 전체 합은 다음과 같이 정리할 수 있습니다.
Σ j × (A[j]/j) = Σ A[j]
즉, 배열을 어떤 순서로 재배열하더라도 전체 합은 배열 모든 요소의 단순한 합과 동일합니다. 결국 이 문제는 "배열 요소들의 합이 m과 같은가?"를 묻는 것과 같으며, 배열을 실제로 재배열해 볼 필요조차 없습니다.
풀이 절차
위 아이디어를 바탕으로 다음 단계로 문제를 해결할 수 있습니다.
- 합계 변수 sum을 0으로 초기화합니다.
- 배열 A의 모든 요소를 순회하면서 sum에 차례대로 더합니다.
- sum이 m과 같으면 true를, 그렇지 않으면 false를 반환합니다.
의사 코드로 표현하면 다음과 같습니다.
sum := 0
n := A의 크기
for i := 0부터 n 미만까지, i를 1씩 증가시키며 반복:
sum := sum + A[i]
if sum이 m과 같다면:
return true
그렇지 않으면
return false
C++ 구현 예제
아래 구현 예제를 통해 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A, int m) {
long sum = 0;
int n = A.size();
for (int i = 0; i < n; ++i) {
sum += A[i];
}
if (sum == m)
return true;
else
return false;
}
int main() {
vector<int> A = { 2, 5, 1 };
int m = 8;
cout << solve(A, m) << endl;
}
입력
{ 2, 5, 1 }, 8
출력
1
복잡도 분석
이 풀이는 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간을 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다. 배열의 크기가 커져도 매우 효율적으로 동작합니다.