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

[Gold V] 등차수열 변환 - 17088

문제 링크

성능 요약

메모리: 27856 KB, 시간: 336 ms

분류

브루트포스 알고리즘, 수학

문제 설명

크기가 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을 출력한다.

---

분석

등차수열의 특징을 이용해야 하는 수학 문제다.

등차수열 : 연속하는 두 항의 차이가 모두 일정한 수열

공차를 선정해서 0번째 인덱스부터 공차를 더해 N번까지 가는데 등차에 해당하는 모든 경우를 따져보면 된다.
처음에는 문제에서 요구하는 `연산` 이 1을 더하거나 빼는 것이라는 것을 체크하지 못했는데 경우의 수를 줄이는 주요한 포인트이다.
문제에서 0, 1번째에서 생성가능한 등차의 경우를 구해서 나머지 모든 경우 O(N) 에서 적용해보면 된다.
생성 가능한 등차는 `연산 방법`에 따라 (0번째에 +1, -1, 가만히 둔 경우) * (1번째에 +1, -1, 가만히 둔 경우) = 9가지

* 첫 번째 항 -1, 두 번째 항 -1
* 첫 번째 항 -1, 두 번째 항 0
* 첫 번째 항 -1, 두 번째 항 +1
* 첫 번째 항 0, 두 번째 항 -1
* 첫 번째 항 0, 두 번째 항 0
* 첫 번째 항 0, 두 번째 항 +1
* 첫 번째 항 +1, 두 번째 항 -1
* 첫 번째 항 +1, 두 번째 항 0
* 첫 번째 항 +1, 두 번째 항 +1

공차를 구했다면 Array를 순회하면서 0번째부터 등차를 더한 값과 연산을 하여 해당 인덱스 값이 같아질 수 있는지 체크하면 된다.

시간 복잡도는 O(N) 100000 * 9(등차의 경우)라서 900000. 1초 안에 가능하다.

---

코드

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


public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        if (N == 1) {
            System.out.println(0);
            System.exit(0);
        }

        int ans = -1;

        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                int change = 0;
                if(i != 0) change++;
                if(j != 0) change++;
                int num1 = arr[1] + i;
                int num0 = arr[0] + j;

                //합의된 등차
                int diff = num1 - num0;

                boolean ok = true;
                int target = num0 + diff; //[0]번 + 선택한 등차 = [1]번
                for (int k = 2; k < N; k++) {
                    target += diff; // [1]번 + 등차 = 2번 이후 계속 진행

                    if (arr[k] + 1 == target) {
                        change++;
                    } else if (arr[k] - 1 == target) {
                        change++;
                    } else if (arr[k] == target) {
                        continue;
                    }else{
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    if (ans == -1 || ans > change) {
                        ans = change;
                    }
                }
            }
        }
        System.out.println(ans);

    }
}