[백준] 17088 등차수열 변환 - Brute Force / Java

• 문제 링크

17088번: 등차수열 변환

 

• 풀이 과정

등차수열의 공차는 모든 항에 대해서 일치하므로,

수열의 첫째, 둘째 항의 공차의 값에 따라 다른 모든 항의 공차를 일치하게 연산할 수 있는지 확인한다.

 

첫째, 둘째 항 각각에 -1, 0, 1 를 더하는 경우, 즉 3 * 3 = 9가지의 경우를 가지므로

2중 for문 내부에 clone() 함수를 통해 배열을 초기화하여 각각의 경우의 공차를 구한다.

 

해당 공차가 나머지 2 ~ n 번째 항의 공차와 일치하는지 검사하며,

항에 더하는 값이 0 이 아닐 시 연산을 적용한 것이므로

각각의 연산의 횟수 cnt 변수에 cnt++ 을 수행한다.

 

이렇게 모든 항에 대하여 공차의 일치 여부에 따라 연산의 횟수의 최솟값 min 과 구해진 cnt 를 비교 및 갱신하여,

최종적으로 min 값을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    static int n, cnt;
    static int[] arr;

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

        n = Integer.parseInt(br.readLine());
        if (n == 1) {
            bw.write(0 + "\n");
            bw.flush();
            return;
        }

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

        int min = Integer.MAX_VALUE;
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                arr = input.clone();
                cnt = 0;

                if (i != 0)
                    cnt++;
                if (j != 0)
                    cnt++;

                arr[0] += i;
                arr[1] += j;
                int gap = arr[1] - arr[0];

                if (check(gap))
                    min = Math.min(min, cnt);
            }
        }

        bw.write((min == Integer.MAX_VALUE ? -1 : min) + "\n");
        bw.flush();
    }

    private static boolean check(int gap) {
        for (int i = 2; i < n; i++) {
            int curGap = arr[i] - arr[i - 1];

            boolean flag = false;
            for (int j = -1; j <= 1; j++) {
                if (curGap + j == gap) {
                    if (j != 0)
                        cnt++;

                    arr[i] += j;
                    flag = true;

                    break;
                }
            }

            if (!flag)
                return false;
        }

        return true;
    }

}