[백준/이분탐색] 1994번 등차수열 (JAVA)

문제

---

풀이

이틀동안 삽질한 문제..! 만만하게 봤는데 여러모로 예외가 많아서 힘들었다!
풀이 접근은 아래와 같다.

1. 등차수열을 만들거니까 일단 주어진 배열을 정렬하고 그 안에서 선택하도록 한다.
2. dp[i][j]에는 arr[j] - arr[i]을 공차로 갖는 등차수열의 최대 길이를 저장한다.
3. j 다음에 올 수의 인덱스는 이분 탐색으로 찾는다.

dp 배열을 활용하고 재귀적으로 호출하는 것은 스스로 생각해내지 못했다. 아쉽다..흑

1차 실패

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

public class Main {

    private static final int MAX_SIZE = 2000;
    private static final int INVALID = -1;
    private static final int INIT = 0;

    private static int n;
    private static int[] arr = new int[MAX_SIZE + 1];
    private static int[][] dp = new int[MAX_SIZE + 1][MAX_SIZE + 1];

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

        parseInput(br);
        int maxLength = findLongestApLength();
        bw.append(String.valueOf(maxLength));

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

    private static void parseInput(BufferedReader br) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) arr[i + 1] = Integer.parseInt(br.readLine());
        Arrays.sort(arr, 1, n + 1);
    }

    private static int findLongestApLength() {
        int max = 1;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                max = Math.max(max, dp(i, j));
        return max;
    }

    private static int dp(int i, int j) {
        int result = dp[i][j];
        if (result != INIT) return result;

        int index = findIndex(arr[j] + arr[j] - arr[i], j + 1);

        if (index == INVALID) return dp[i][j] = 2;
        else return dp[i][j] = dp(j, index) + 1;
    }

    private static int findIndex(int target, int start) {
        int left = start, right = n, mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] == target) return mid;

            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return INVALID;
    }
}

이 코드를 디버깅하면서 찾은 반례는 5 1 1 1 1 2였다. 답이 4가 나와야 하는데 3이 나왔다. 아무래도 findIndex()의 인덱싱 문제인 것 같아서 디버깅을 하면서 잘못된 부분을 고쳐봤다.

위의 코드는 같은 수가 여러 개 있을 때 가장 왼쪽의 값을 찾지 못한다는 함정이 있었다. 이를 해결하기 위해 arr[left] == target이면 left를 반환하는 조건을 추가했다.

그리고 문제에서 제공한 테케 5 1 4 3 5 7같은 경우를 위해 arr[mid] == target이면 mid를 반환하는 조건도 추가했다.

그랬더니 채점 중간에 스택오버플로우가 떴다. dp()가 무한호출되는 문제였다. 재귀인데 종료 조건이 없어서 무한재귀호출이 되고 있는 거였다. 그래서 i, j에 따른 종료조건을 추가했고 통과할 수 있었다.

성공

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

public class Main {

    private static final int MAX_SIZE = 2000;
    private static final int INVALID = -1;
    private static final int INIT = 0;

    private static int n;
    private static int[] arr = new int[MAX_SIZE + 1];
    private static int[][] dp = new int[MAX_SIZE + 1][MAX_SIZE + 1];

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

        parseInput(br);
        int maxLength = findLongestApLength();
        bw.append(String.valueOf(maxLength));

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

    private static void parseInput(BufferedReader br) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) arr[i + 1] = Integer.parseInt(br.readLine());
        Arrays.sort(arr, 1, n + 1);
    }

    private static int findLongestApLength() {
        int max = 1;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                max = Math.max(max, dp(i, j));
        return max;
    }

    private static int dp(int i, int j) {
        if (i > j) return 0;
        else if (i == j) return 1;

        int result = dp[i][j];
        if (result != INIT) return result;

        int target = 2 * arr[j] - arr[i];
        int index = findIndex(target, j + 1);

        if (index == INVALID) return dp[i][j] = 2;
        else return dp[i][j] = dp(j, index) + 1;
    }

    private static int findIndex(int target, int start) {
        int left = start, right = n, mid = (left + right) / 2;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        if (left <= n && arr[left] == target) return left;
        if (arr[mid] == target) return mid;
        else return INVALID;
    }
}

DP 어렵다.. 이분탐색 어렵다...

---

참고

[백준] 1994번 등차수열