https://www.acmicpc.net/problem/3273
주어진 배열에서 합이 X가 되는 쌍의 개수를 구하는 문제

🥲 dfs 조합으로 풀이시 시간초과 발생 !

public class Song3273 {
    static int N;
    static int[] arr;
    static int X;
    static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        X = Integer.parseInt(br.readLine());

        findCombinations(0, 0, 0);
        System.out.println(ans);
    }

    private static void findCombinations(int idx, int selectedCount, int currentSum) {
        // 종료 조건
        if (selectedCount == 2) {
            if (currentSum == X) {
                ans++;
            }
            return;
        }

        // 조합 생성
        for (int i = idx; i < N; i++) {
            findCombinations(i + 1, selectedCount + 1, currentSum + arr[i]);
        }
    }
}

주어진 코드는 모든 가능한 조합을 DFS를 통해 생성하고, 합이 X인 경우를 찾아내는 방식으로 문제를 해결하려고 합니다. 그러나 이러한 방식은 입력의 크기가 커질수록 시간 복잡도가 급격하게 증가하게 되어 시간 초과가 발생할 수 있습니다.

빅 오 표기법에서 이 코드의 시간 복잡도를 나타내면 O(2^N)이 됩니다. 여기서 N은 배열의 크기를 의미.

백준 3273번 문제에서 주어진 입력 범위에 대해 고려해보면, N이 최대 10,000까지 가능합니다. 따라서 O(2^N)의 시간 복잡도는 매우 큰 값이 되어 효율적으로 해결하기 어려워집니다.

풀이

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

public class Song3273 {
    static int N;
    static int[] arr;
    static int X;
    static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        X = Integer.parseInt(br.readLine());

        Arrays.sort(arr); // 정렬!

        int left = 0, right = N - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == X) {
                ans++;
                left++;
                right--;
            } else if (sum < X) {
                left++;
            } else {
                right--;
            }
        }


        System.out.println(ans);
    }



}