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

 

#풀이

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

public class Main {
        static int N;
        static int[] arr;
        static int ans = -1;
        static int[] dx = {-1,0,1};
    static int check(int dif, int now,int add){
        int sum = add;
        int index = 2;
        while(true){
            if(index==arr.length)break;
            if(arr[index]-now == dif){
                now = arr[index];
                index++;

            }
            else if(arr[index]+1-now == dif){
                now = arr[index]+1;
                index++;
                sum++;
            }
            else if(arr[index]-1-now == dif){
                now = arr[index]-1;
                index++;
                sum++;
            }
            else{
                sum = -1;
                break;
            }
        }
        return sum;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for(int i = 0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        if(N==1){
            System.out.println("0");
            return;
        }

        for(int i = 0; i<3; i++){
            int add1 = 0;
            int first = arr[0]+dx[i];
            if(dx[i]!=0)add1++;
            for(int j = 0; j<3; j++){
                int add2 = 0;
                if(dx[j]!=0)add2++;
                int second = arr[1]+dx[j];
                int dif = second - first;
                int temp = check(dif,second,add1+add2);
                if(temp!=-1){
                    if(ans==-1)ans = Integer.MAX_VALUE;
                    ans = Math.min(ans,temp);
                }
            }
        }
        System.out.println(ans);
    }
}

#성능

#정리

1. arr[0]과 arr[1]에 대해 각각 -1, 0, +1을 한 번씩 적용해 총 9가지 조합을 만든다.

2. 각 조합마다 조정된 두 수의 차이를 공차(dif)로 설정하고, 초기 연산 횟수(±1 한 횟수)를 기록한다.

3. 세 번째 원소부터 순차적으로 현재 값이 공차에 맞는지 확인하고(안맞으면 +1,-1 한 값도 비교), 맞지 않으면 해당 조합은 실패로 간주한다.

4. 가능한 조합 중에서 필요한 연산 횟수가 가장 적은 경우를 최종 정답으로 선택한다. (가능한 조합이 없다면 -1을 출력한다.)