🌠"등차수열 변환" - 17088번 G4

🎃문제설명

크기가 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 ≤ 10^5)$이 주어진다. 둘째 줄에는 B1, B2, ..., BN$(1 ≤ Bi ≤ 10^9)$이 주어진다.

출력

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

💾입출력 예

입력	출력
4 24 21 14 10	3
2 5 5	0
3 14 5 1	-1
5 1 3 6 9 12	1

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 브루트포스 알고리즘

🌟문제 이해 및 풀이계획

✏️모든 수를 검사하기에는 -1, 0, +1 세가지 경우를 $10^5$번 해야해므로 총 $3^{10000}$번이 된다. 따라서 모든 경우를 검사하는 건 불가능하다.

✏️어떤식으로 해야 모든 수를 검사하지 않고 답을 도출할 수 있을 지 생각하다가 공차를 이용해보기로 했다. 등차수열이 되려면 수들의 차가 모두 같아야 하므로 공차 배열을 따로 두었다.

✏️공차의 차가 4초과이면 최대 +1, -1 해야하므로 등차수열이 될 수 없음을 이용하여 -1을 미리 출력해주었다.

✏️공차의 차의 배열까지 다시 정해서 해야하나 하다가 풀이가 떠오르지 않아 강의를 들었다.

강의내용

✔️0번째와 1번째 수가 정해지면 2번째 수 부터는 앞에서 정해진 공차에 맞춰 알아서 정해진다. 따라서 $3^2$가지 경우만 생각해보면 된다.

✔️이때, 범위안에 들어오지 못하는 경우가 있으면 -1을 출력해주면 된다.

⚔️배열 길이가 1인 경우는 미리 빼주고, clone()을 이용하여 원래 숫자 배열을 바꿔도 영향이 가지 않게 해준다. (9가지 경우를 검사할 때 배열을 항상 초기화 시켜주지 않으면 틀린 답이 나온다!)

✍🏻내 코드 - 정답코드

package BOJ;

import java.util.Scanner;

/*
 * 2021.12.20 daily algo/commit
 * 
 * Brute Force
 * 1,2번째 수에 어떻게 적용할 지만 알면 3번째부터는 정해지므로 (+1, -1, 0) 3^2가지 경우만 생각하면 된다.
 */

public class boj_17088 {
	
	static int min = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] B = new int[N];
		int[] b = new int[N-1]; // 차이 배열
		for(int i=0; i<N; i++) {
			B[i] = sc.nextInt();
		}
		sc.close();
		
		if(B.length == 1) {
			System.out.println(0);
			return;
		}
		
		for(int i=0; i<N-1; i++) {
			b[i] = Math.abs(B[i]-B[i+1]);
			// 차이가 4 이상이면 등차수열 불가능
			if(i > 0 && Math.abs(b[i-1]-b[i]) > 4) {
				System.out.println(-1);
				return;
			}
		}
		
		for(int i=-1; i<=1; i++) {
			for(int j=-1; j<=1; j++) {
				int cnt = 0;
				int[] BB = B.clone();
				BB[0] += i; // 첫 번째 수
				BB[1] += j; // 두 번째 수
				if(i != 0) cnt += 1;
				if(j != 0) cnt += 1;
				int ans = check(BB, BB[1]-BB[0], 0);
				if(ans == -1) continue;
				ans += cnt;
				if(min > ans) min = ans;
			}
		}
		System.out.println(min);
	}

	public static int check(int[] BB, int d, int cnt) {
		for(int i=1; i<BB.length-1; i++) {
			int diff = BB[i+1] - BB[i];
			if(diff != d) {
				if(Math.abs(diff-d) > 1) return -1;
				BB[i+1] += (d-diff);
				cnt += 1;
			}
		}
		return cnt;
	}
}