[BOJ 17088] 등차수열 변환 (Java)

BOJ 17088 등차수열 변환

문제풀이

이전에 비슷한 문제를 완전탐색으로 풀었어서 이번에도 완전탐색을 시도해봤다. BFS로 최소 변환 수를 찾아보려했는데 일단 메모리 초과가 나왔고 변형을 거듭하다가 DFS로 바꾸어 구현했을 때는 시간 초과가 났다.

애초에 수열의 크기가 10^5이며 각 수는 [-1, 0, 1]을 더할 수 있으므로 최악의 경우에 3^10^5번의 연산을 해야하기 때문에 완전탐색은 적절하지 않았다.

결국 다른 분들의 풀이법을 참고하고 나서야 풀이할 수 있었다.

• 등차수열은 처음부터 끝까지 차이가 같아야한다. (공차)
• 따라서 첫 번째와 두 번째 항에 [-1, 0, 1]의 수를 더했을 때 나오는 각 3가지 경우를 가지고 총 9가지 경우를 만들 수 있다.
• 9가지 경우는 각각 공차를 가지며 세 번째 항 부터는 공차와 같은 차이를 만들어내는지 확인하는 방식으로 진행하면 된다.

구현코드

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		
		if(N == 1) {
			System.out.println(0);
			return;
		}
		
		int[] numbers = new int[N];
		int ans = Integer.MAX_VALUE;
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; ++i) numbers[i] = Integer.parseInt(st.nextToken());

		for(int i = -1 ; i <= 1 ; ++i) {
			for(int j = -1 ; j <= 1 ; ++j) {
				
				int[] arr = numbers.clone();
				int cnt = 0;
				boolean success = true;
				
				if(i != 0) cnt++;
				if(j != 0) cnt++;
				
				arr[0] += i;
				arr[1] += j;
				int diff = arr[1] - arr[0];
				
				for(int k = 2 ; k < N ; ++k) {
					
					int curDiff = arr[k] - arr[k - 1];
					boolean flag = false;
					
					for(int l = -1 ; l <= 1 ; ++l) {
						if(curDiff + l == diff) {
							if(l != 0) cnt++;
							
							arr[k] += l;
							flag = true;
							
							break;
						}
					}
					
					if(!flag) {
						success = false;
						break;
					}
				}
				if(success) ans = ans > cnt ? cnt : ans;
			}
		}
		if(ans == Integer.MAX_VALUE) ans = -1;
		System.out.println(ans);
	}
}