[Java] 백준 17088번 등차수열 변환

수열이 주어질때 규칙에 따라 등차수열로 변화시킬 수 있는지 찾는 문제입니다.

등차수열은 수열의 수의 앞뒤의 차가 전부 같은 수열을 말합니다.
수열이 주어지고 각 수에 1을 빼거나 1을 더할 수 있습니다.

가능한 경우
1. 현재 수 1 빼기
2. 현재 수 그대로 사용
3. 현재 수 1 더하기

위의 3가지 경우를 모두 DFS로 탐색하였습니다.
그리고 이전의 값과 차가 동일하면 계속 DFS로 탐색합니다.

가능한 경우들이 여러개가 나오는데 최소의 연산을 한 경우를 출력해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
  static int result = 987654321;

  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];

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

    if (n <= 2) {
      result = 0;
    } else {
      dfs(arr, 2, arr[0] - 1 - (arr[1] - 1), arr[1] - 1, 2);
      dfs(arr, 2, arr[0] - 1 - arr[1], arr[1], 1);
      dfs(arr, 2, arr[0] - (arr[1] - 1), arr[1] - 1, 1);

      dfs(arr, 2, arr[0] + 1 - (arr[1] - 1), arr[1] - 1, 2);
      dfs(arr, 2, arr[0] - arr[1], arr[1], 0);
      dfs(arr, 2, arr[0] - 1 - (arr[1] + 1), arr[1] + 1, 2);

      dfs(arr, 2, arr[0] + 1 - (arr[1] + 1), arr[1] + 1, 2);
      dfs(arr, 2, arr[0] + 1 - arr[1], arr[1], 1);
      dfs(arr, 2, arr[0] - (arr[1] + 1), arr[1] + 1, 1);

      result = result == 987654321 ? -1 : result;
    }

    bw.write(result + "");
    bw.close();
  }

  public static void dfs(int[] arr, int index, int num, int prev, int cnt) {
    if (arr.length == index) {
      result = Math.min(result, cnt);
      return;
    }
    if (prev - arr[index] == num) {
      dfs(arr, index + 1, num, arr[index], cnt);
    }
    if (prev - (arr[index] + 1) == num) {
      dfs(arr, index + 1, num, (arr[index] + 1), cnt + 1);
    }
    if (prev - (arr[index] - 1) == num) {
      dfs(arr, index + 1, num, (arr[index] - 1), cnt + 1);
    }
  }
}