[백준] 2295번 : 세 수의 합

 

https://www.acmicpc.net/problem/2295

 

💡 접근법

• N은 1000보다 작은 값이지만, 시간 단위가 1초이기 때문에 시간 초과를 고려해야 한다

 

임의의 3개의 수를 어떻게 고를지가 관건인데

 

3, 4, 8, 10, 15, 18, 20 이라고 생각해보면

{3,4,8} {3,4,10} {3,4,15} 이렇게 끝 값을 하나씩 옮겨가면서 처음에 케이스를 구하게 되는 걸 보면

결국 2개의 값을 어떻게 구하는지가 중요하구나! 라는 생각이 들게 된다.

2개를 구하고 저장해두었다면 그 값들만 가지고 만들 수 있는 수가 있는지만 찾으면 된다!

• 2개의 덧셈 값을 구하고, 나머지 하나의 값을 끼워맞춘다
• 덧셈 값을 일반 배열에 넣으면 중복값이 늘어날 것이기 때문에 set 자료구조를 사용하도록 하자

이 문제의 조건에서 특이한 점은 x, y, z, k가 서로 같아도 된다. 라는 조건이다

무슨 뜻인가 한참 헷갈렸는데, 4+8+8 = 20 처럼 두 개의 숫자가 같아도 된다는 뜻. (8+8+8도 가능)

x,y,z 가 모두 자연수기 때문에 k가 같을 수는 없을 것 같다.

 

아무튼 이 조건 덕분에,

• 어떤 값을 골랐는지는 추적할 필요가 없다. 똑바로 3개가 더해졌는지만 알면 된다
• 나머지 하나의 값을 끼워넣는 것이 더 쉬워진다

 

➕ 짚고 넘어가기

• next_permutation 은 n! / (n-k)! 이기 때문에 이 문제에서 k=3 이 되어 O(n^3) 으로 시작하고 만다
  
  • 2개인 경우에서는 사용해도 좋을 수 있지만, 3개부터는 신중하게 사용하는게 좋을듯함 (처음부터 대차게 이 함수를 썼다가 시간초과를 당했다)
  • 오름차순으로 정렬 (0 0 0 1 1), 선택하는 인자를 0으로 설정하는 것도 은근 헷갈린다
• Set 자료구조도 다시 살펴보자
  • 내부적으로는 Red-Black Tree를 쓰고 있다고
  • set.count(key) 를 쓰면 Set 은 무조건 값을 0개 아니면 1개만 가지기 때문에 find 와 같은 용도로 쓸 수 있다 ! 신기
    • 물론 find와 시간 차이는 별로 안나는 듯 하다. 둘다 O(logN) 인듯

---

✏️ 나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

/*
7
3
4
8
10
15
18
20
*/

int main() {
    int N;
    cin >> N;

    vector<int> Input(N);
    for (int i = 0;i < N;i++)
    {
        cin >> Input[i];
    }
    sort(Input.begin(), Input.end());

    set<int> Combo;

    for (int i = 0;i < N;i++)
    {
        for (int j = i;j < N;j++)
        {
            Combo.insert(Input[i] + Input[j]);
        }
    }

    int Answer = 0;
    for (int i = N-1;i >= 0;i--)
    {
        for (int j = 0;j < i;j++)
        {
            int PotentialNumber = Input[i] - Input[j];
            if (Combo.count(PotentialNumber) != 0)
            {
                Answer = max(Input[i], Answer);
                break;
            }
        }
    }

    cout << Answer << "\n";
    return 0;
}