백준 2295 c++ "세 수의 합" -PlusUltraCode-

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

[필자 사고]

재미난 문제다. 3수를 브루트포스 뭐 백트래킹을 이용하면 시간초과가 난다. 

해결방법이 없을까?? 

일단 2수를 미리 더해놓은 배열을 만들어 놓은다. 

그리고 마지막에 2중포문을 돌아서 

큰수 - 다른 아무 수 = findNum 의 식을 만든 뒤 

findNum을 아까 2수를 더해놓은 배열에서 이진탐색을 통해 찾는다. 

 

이런 사고가 점점 자유롭게 될 때 까지 연습해보자.

[코드 해설]

main 함수의 전체 흐름

main 함수 안에서 문제의 모든 과정을 처리합니다. 핵심 단계는 다음과 같습니다.

1. 입력 처리
2. 배열 정렬
3. 두 수의 합을 저장하는 보조 배열 생성
4. 조건을 만족하는 가장 큰 수 탐색
5. 결과 출력

---

입력 처리 부분

• 변수 N에 자연수 개수를 입력받습니다.
• 이어서 N개의 수를 입력받아 arr 벡터에 저장합니다.

이 단계에서 입력 집합 U를 벡터 형태로 프로그램 안에 준비하는 것입니다.

---

정렬 과정

• arr를 오름차순으로 정렬합니다.
• 문제에서 특정한 순서가 필요하지는 않지만, 뒤에서 큰 값부터 탐색하거나 이분 탐색을 쓰기 위해 정렬이 필요합니다.

---

두 수의 합을 저장하는 과정

• i를 0부터 N-1까지, k를 i 이상부터 N-1까지 돌면서
  arr[i] + arr[k] 값을 구하고 sumArr에 저장합니다.
• 이렇게 하면 집합 U 안의 두 수의 합을 모두 구하게 됩니다.
• 자기 자신을 두 번 더하는 경우도 포함됩니다. 문제에서 인덱스가 같아도 된다고 했으므로 이 방식이 맞습니다.

---

두 수의 합 배열 정렬

• sumArr를 정렬합니다.
• 이렇게 정렬해 두면 특정 값이 존재하는지 여부를 이분 탐색으로 빠르게 확인할 수 있습니다.

---

최적해 탐색 과정

• 큰 수부터 내려가며 확인하기 위해 arr의 마지막 원소부터 시작합니다.
• 특정 원소 arr[i]를 선택했을 때, 이 수가 세 수의 합으로 표현될 수 있는지 확인합니다.
• 이를 위해 다시 k를 돌면서 findNum = arr[i] - arr[k] 값을 계산합니다.
• 이 값이 sumArr 안에 존재한다면, 즉 두 수의 합이 findNum인 경우가 있다면,
  arr[i] = arr[k] + (두 수의 합) 꼴이 성립합니다. 따라서 세 수의 합으로 표현 가능합니다.
• 조건을 만족하는 순간, answer를 갱신합니다.
• 큰 값부터 내려오기 때문에 가장 먼저 발견되는 값이 곧 최적해입니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int N;
vector<ll> arr;
vector<ll> sumArr;

int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		ll num;
		cin >> num;
		arr.push_back(num);
	}

	sort(arr.begin(), arr.end());
	for (int i = 0; i < arr.size(); i++) {
		for (int k = i ; k < arr.size(); k++) {
			ll sum = arr[i] + arr[k];
			sumArr.push_back(sum);
		}
	}

	sort(sumArr.begin(), sumArr.end());
	ll answer = -1;
	for (int i = N-1; i>=0; i--) {
		for (int k = 0; k < arr.size(); k++) {
			ll findNum = arr[i] - arr[k];
			if (binary_search(sumArr.begin(), sumArr.end(), findNum)) {
				answer = max(answer, arr[i]);
			}
		}
	}
	cout << answer;
}