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

문제 링크

https://www.acmicpc.net/problem/17088

문제

크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]은 등차수열이 아니다.

수열 B = [B1, B2, ..., BN]을 등차수열로 변환하려고 한다. 각각의 수에는 연산을 최대 한 번 적용할 수 있다. 연산은 두 가지가 있는데, 1을 더하거나 1을 빼는 것이다. 수열 B를 등차수열로 변환하기 위해 필요한 연산 횟수의 최솟값을 구해보자.

입력

첫째 줄에 수열 B의 크기 N(1 ≤ N ≤ 105)이 주어진다. 둘째 줄에는 B1, B2, ..., BN(1 ≤ Bi ≤ 109)이 주어진다.

출력

수열 B를 등차수열로 변화시키기 위한 연산 횟수의 최솟값을 출력한다. 등차수열로 변환시킬 수 없다면 -1을 출력한다.

알고리즘: 브루트포스

풀이

B 수열에서 첫 번째 수와 두 번째 수의 차를 가지고 B 수열에 적용해본다.

첫 번째 수와 두 번째 수의 차는 총 9가지다.
fn + 0, sn + 0
fn + 0, sn + -1
fn + 0, sn + 1

fn + -1, sn + 0
fn + -1, sn + -1
fn + -1, sn + 1

fn + 1, sn + 0
fn + 1, sn + -1
fn + 1, sn + 1

9개의 등차를 B 수열에 적용해서 count 해본다. 그중 가장 작은 값을 출력

소스 코드

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

public class Main {
    static int N;
    static long B[];
    static long w[] = {0,-1,1};
    static long count = 100001;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        B = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            B[i] = Long.parseLong(st.nextToken());
        }
        if (N <= 2) System.out.println(0);
        else {
            for (int i = 0; i < w.length; i++) {
                long fn = B[0] + w[i];
                for (int j = 0; j < w.length; j++) {
                    long sn = B[1] + w[j];
                    long n_cout = check(sn ,fn-sn);
                    if(n_cout != -1) {
                        n_cout += Math.abs(w[i]) + Math.abs(w[j]);
                        if(count > n_cout) count = n_cout;
                    }
                }
            }
            if(count == 100001) System.out.println(-1);
            else System.out.println(count);
        }
    }
    
    static long check(long bn, long d) {
        long cout = 0;
        for(int i=2; i<N; i++) {
            boolean ctn = false;
            for(int j=0; j<w.length; j++) {
                if(bn-(B[i]+w[j]) == d) {
                    bn = B[i]+w[j];
                    cout += Math.abs(w[j]);
                    ctn = true;
                    break;
                }
            }
            if(!ctn) return -1;
        }
        return cout;
    }
}