[백준] 1994: 등차수열 (Java)

등차수열

백준 1994 Gold III DP · 정렬

문제 분석

• N개의 음이 아닌 정수 중 일부를 골라 나열했을 때, 만들 수 있는 가장 긴 등차수열의 길이를 구하는 문제
• 등차수열의 공차는 양수, 0, 음수 모두 가능
• 원소를 자유롭게 나열할 수 있으므로, 정렬 후 가장 긴 등차 부분수열(LAS)을 찾으면 된다
• 제약: N ≤ 2,000 / 값 ≤ 10⁹

접근법

DP on sorted pairs — O(N²)

정렬된 배열에서 dp[i][j]를 "인덱스 i, j를 마지막 두 원소로 하는 등차수열의 최대 길이"로 정의한다.

• 공차 d = a[j] - a[i]이면, 직전에 와야 할 원소는 a[i] - d = 2·a[i] - a[j]
• j를 고정하고 i를 0 → j-1로 순회하면서, HashMap으로 target 값의 가장 최근 인덱스 k를 O(1)에 조회
• k가 존재하면 dp[i][j] = dp[k][i] + 1, 없으면 dp[i][j] = 2

왜 가장 최근 인덱스(rightmost k)인가?

중복 값이 있을 때, k2 > k1이면 dp[k2][i]의 탐색 범위가 dp[k1][i]보다 넓으므로 항상 dp[k2][i] ≥ dp[k1][i]가 성립한다. 따라서 rightmost k를 선택하는 것이 최적이다.

풀이 (Java)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(br.readLine().trim());
        }

        // 원소가 2개 이하면 전부 등차수열
        if (N <= 2) {
            System.out.println(N);
            return;
        }

        Arrays.sort(a);

        // dp[i][j] = a[i], a[j]를 마지막 두 원소로 하는 등차수열 최대 길이
        int[][] dp = new int[N][N];
        int ans = 2;

        for (int j = 1; j < N; j++) {
            // j 이전 인덱스들의 값 → 가장 최근 인덱스 매핑
            HashMap<Long, Integer> map = new HashMap<>();

            for (int i = 0; i < j; i++) {
                // a[i] 앞에 와야 할 원소: 2*a[i] - a[j]
                long target = 2L * a[i] - a[j];
                Integer k = map.get(target);

                if (k != null) {
                    dp[i][j] = dp[k][i] + 1; // 기존 수열에 a[j] 추가
                } else {
                    dp[i][j] = 2; // a[i], a[j] 두 원소로 시작
                }

                if (dp[i][j] > ans) ans = dp[i][j];
                map.put((long) a[i], i); // i 처리 후 map에 등록 (k < i 보장)
            }
        }

        System.out.println(ans);
    }
}

예제 트레이스

입력: [1, 4, 3, 5, 7]
정렬: [1, 3, 4, 5, 7]

j=3 (a[j]=5):
  i=1 (a[i]=3): target = 2×3 - 5 = 1
    → map에 {1:0} 존재, k=0
    → dp[1][3] = dp[0][1] + 1 = 3
    → 등차수열: 1, 3, 5

j=4 (a[j]=7):
  i=3 (a[i]=5): target = 2×5 - 7 = 3
    → map에 {3:1} 존재, k=1
    → dp[3][4] = dp[1][3] + 1 = 4
    → 등차수열: 1, 3, 5, 7  ← 최대!

출력: 4

시간 복잡도

O(N²)

공간 복잡도

O(N²)

클린 코드 — Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        int[] a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = Integer.parseInt(br.readLine().trim());
        if (N <= 2) { System.out.println(N); return; }
        Arrays.sort(a);
        int[][] dp = new int[N][N];
        int ans = 2;
        for (int j = 1; j < N; j++) {
            HashMap<Long, Integer> map = new HashMap<>();
            for (int i = 0; i < j; i++) {
                long t = 2L * a[i] - a[j];
                Integer k = map.get(t);
                dp[i][j] = k != null ? dp[k][i] + 1 : 2;
                if (dp[i][j] > ans) ans = dp[i][j];
                map.put((long) a[i], i);
            }
        }
        System.out.println(ans);
    }
}