백준) 2295 : 세 수의 합

⏰문제

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

2295번: 세 수의 합

문제

N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.

예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다.

입력

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된다. U의 원소는 200,000,000보다 작거나 같은 자연수이다. 답이 항상 존재하는 경우만 입력으로 주어진다.

 

출력

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최대가 되도록 하는 것이 목적이다. x, y, z, k가 서로 같아도 된다. 이때, k번째 수를 출력하면 된다.

예제 입력 1 복사

5
2
3
5
10
18

 

예제 출력 1 복사

18

 

💡풀이

문제에서는 자연수  `U[x] + U[y] + U[z] = U[k]` 라고 나와있고, 이 U[k]는 집합 안에 있어야 된다고 했다. 

하지만 이를 for문으로 무작정 돌리면 시간초과가 나온다. 그래서 위 식을 잘 바꾸어서 이용해야 한다. 

 

U[x] + U[y] + U[z] = U[k]
-> U[x] + U[y] = U[k] - U[z]
-> sum[?] = U[k] - U[z]

 

위와 같이 sum이라는 배열(원본 배열에서 숫자 2개씩 뽑아 더한 배열)을 새로 만든 후에, 원본 배열에서 ` U[k] - U[z]`한 값이 sum이라는 배열에 있는 방식으로 찾는 것이다.

그리고 문제의 출력 부분을 보면 x, y, z, k가 서로 같아도 된다고 했으므로 같은 숫자를 중복으로 사용해도 된다는 것이다. 

그래서 두 수의 합인 sum이라는 배열을 만들 때, for문에서 i와 j의 시작점이 같을 수 있는 것이다. 

 

 

⌨️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
    public static void main(String[] args) throws IOException {
        //1. 입력 값
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] U = new int[N];
        for(int i=0; i< N; i++){
            U[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(U);

        //2. 중복이 가능하므로 가능한 경우의 수는 모두 N*N
        int[] sum = new int[N*N];
        int idx = 0;
        for(int i=0; i< N; i++){
            for(int j = 0; j< N; j++){
                sum[idx++] = U[i]+U[j];
            }
        }
        Arrays.sort(sum);
//        System.out.println(Arrays.toString(sum));

        //3. 이분 탐색
        /*
            U[x] + U[y] + U[z] = U[k]
            -> U[x] + U[y] = U[k] - U[z]
            -> sum[?] = U[k] - U[z]
            U의 차가 sum 배열에 있는지!
         */
      
        int answer = 0;
        outer : for(int i=N-1; i >= 0; i--){
            for(int j = 0; j < i; j++){
                if(Arrays.binarySearch(sum, U[i] - U[j]) >= 0) { //음수로 반환하면 없다는 것
                    answer= U[i];
                    break outer;
                }
            }
        }
        System.out.println(answer);
    }
}

 

 

📣 comment

DFS로 경우의 수를 만들어서 이분탐색을 돌리는 것인 줄 알았는데 간단한 방법이 나와서 놀랬다. 하지만 문제 풀 때 쉽게 도출을 못 했던 방식이라서 잊지말고 공부할 겸 기록으로 남긴다.