물리 실험을 수행하는 상황을 가정해 보겠습니다. n개의 값 쌍과 임계값 k가 주어지며, 각 쌍의 첫 번째 값은 하나의 합계(a)에 더하고, 두 번째 값은 또 다른 합계(b)에 더합니다. 그런 다음 각 합계에 대해 "합계 자체가 더 작은지, 아니면 (k − 합계) 값이 더 작은지"를 비교하여 최솟값을 구하고, 두 결과를 더해 최종 출력하는 것이 목표입니다.
예를 들어 입력이 n = 4, k = 20, values = {{3, 5}, {4, 3}, {2, 1}, {4, 4}}라면 출력은 14가 됩니다.
해결 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 두 개의 변수 a, b를 0으로 초기화합니다.
- n개의 쌍을 순회하면서 첫 번째 값은 a에, 두 번째 값은 b에 누적합니다.
- a와 b 각각에 대해 min(합계, k − 합계)을 계산합니다.
- 두 최솟값을 더한 결과를 출력합니다.
위 과정을 의사 코드로 표현하면 다음과 같습니다.
a := 0, b := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
a := a + first value of values[i]
b := b + second value of values[i]
print(min(a, k - a) + min(b, k - b))C++ 구현 예제
아래는 위 로직을 실제로 구현한 C++ 코드입니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, int k, vector<pair<int,int>> values) {
int a = 0, b = 0;
for(int i = 0; i < n; i++){
a += values[i].first;
b += values[i].second;
}
cout<<min(a, k - a) + min(b, k - b);
}
int main() {
int n = 4, k = 20;
vector<pair<int,int>> values = {{3, 5}, {4, 3}, {2, 1}, {4, 4}};
solve(n, k, values);
return 0;
}입력
4, 20, {{3, 5}, {4, 3}, {2, 1}, {4, 4}}출력
14
결과 분석
코드의 동작을 살펴보면 다음과 같습니다. 첫 번째 값들의 합은 a = 3 + 4 + 2 + 4 = 13이고, 두 번째 값들의 합은 b = 5 + 3 + 1 + 4 = 13입니다. 임계값 k가 20이므로 각각 min(13, 20 − 13) = 7이 되고, 최종적으로 7 + 7 = 14가 출력됩니다.
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리 사용량은 O(1)로 매우 효율적입니다.