서로 다른 두 수의 최소합 O(n) 에 구하기

사실 이건 너무 당연한건데 이 문제 에서 다른 복잡한 식안에 변형되어 숨어있으니

까고보면 이 포스팅의 제목과 같은 문제라는 것을 파악하지 못하여 이 글을 메모삼아 올린다.

가장 무식한 방법은 O(N^2) 로 모든 쌍을 봐주어 최소값을 갱신하는 것이다.

그런데 사실 그냥 N개의 수 중에 가장 작은 두 수의 합이 답이 될 것이다. 그럼

구현하기에는 정렬하여 0번째, 1번째 값의 합을 구하는 O(NlgN) 방식이 제일 깔끔하다.

O(N) 에 구현하려면 사실 두개의 변수를 두어 구현할 수는 있지만 구현 방법에 따라

조건문 처리해주는게 뭔가 귀찮을 수도있다. 이렇게도 한번 생각해 보자.

m = 0~i-1 원소들중 최소값

이기 때문에 m+A[i] 로 답을 갱신하고

m = min(m, A[i]) 로 m을 갱신하는 식으로 반복문을 돌린다. 즉,

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3c3c3c3c;
int main() {
    int A[10] = {1,6,4,7,10,8,5,3,2,9};
    int m = inf;
    int ans = inf;
    for(int i = 0 ; i < 10; i++){
        ans = min(ans, m + A[i]);
        m = min(m, A[i]);
    }
    cout << ans;
    return 0;
}

이런식으로 말이다.