[백준 자바] 2295번(세 수의 합)

난이도 - 골드 4

문제

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번째 수를 출력하면 된다.

 

---

 

 

728x90

시도1 )

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];

for (int i = 0; i < N; i++)
	arr[i] = Integer.parseInt(br.readLine());

Arrays.sort(arr);

int max = 0;

for (int i = N - 1; i >= 0; i--) {
	for (int j = i; j >= 0; j--) {
		int sum = arr[i] + arr[j];
		if (sum >= arr[N - 1])
			break;

		for (int k = j; k >= 0; k--) {
			int result = sum + arr[k];
			if (Arrays.binarySearch(arr, result) >= 0) {
				max = Math.max(max, result);
			}
		}
	}
}
bw.write(String.valueOf(max));

• 원소들을 배열에 오름차순으로 넣고 두 수를 선택한다. 이 때 두 수의 합이 배열의 최댓값보다 크면 더 볼 필요도 없으므로 다른 두 수를 선택한다.
• 나머지 하나도 마저 택하고 binarySearch를 이용하여 선택된 세 수의 합이 배열에 있는지 확인한다.
• 배열에 있고 max값보다 크면 그 수를 max로 갱신한다.

딱히 틀린 이유가 없어보이는데 83%에서 계속 틀렸습니다가 뜬다. (아직도 이유는 모르겠음..)

 

위에서 한 방법은 문제 그대로 x+y+z=k의 최대를 찾는 것이었다. 이 식은 x+y=k-z로 쓸 수 있다.

최댓값 k를 찾아야 하므로 k는 배열의 역순으로 for문을 돌리고 k-z를 만족하는 x+y가 있으면 즉시 k를 리턴하고 반복문을 나온다. 이 방법을 위해 x+y값들을 저장하는 set을 생성했다.

 

최종코드)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(br.readLine());

        Arrays.sort(arr);

        Set<Integer> set = new HashSet<>();

        for (int i : arr)
            for (int j : arr)
                set.add(i + j);

        for (int k = N - 1; k >= 0; k--) {
            for (int z : arr) {
                if (set.contains(arr[k] - z)) {
                    bw.write(String.valueOf(arr[k]));
                    bw.flush();
                    return;
                }
            }
        }

        br.close();
        bw.close();
    }
}