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

=====

문제 풀이

숫자 배열에서 각 인덱스에 적힌 숫자를 -1 ,0 ,+1 계산이 가능하며 그 다음 인덱스와의 차이가 등차수열의 공차가 되어 다음 인덱스에 적힌 숫자와의 차이가 공차가 되는지 확인하는 문제이다. -1,0,+1 중 0 은 연산이 일어나지 않은 경우이다.

첫번째와 두번째 인덱스에 적힌 숫자로 만들수 있는 조합은 아래와 같다.

const n = arr[0];
const n1 = n - 1n;
const n2 = n + 1n;

const nn = arr[1];
const nn1 = nn - 1n;
const nn2 = nn + 1n;

dfs(nn, 1, nn - n, 0);
dfs(nn, 1, nn - n1, 1);
dfs(nn, 1, nn - n2, 1);

dfs(nn1, 1, nn1 - n, 1);
dfs(nn1, 1, nn1 - n1, 2);
dfs(nn1, 1, nn1 - n2, 2);

dfs(nn2, 1, nn2 - n, 1);
dfs(nn2, 1, nn2 - n1, 2);
dfs(nn2, 1, nn2 - n2, 2);

위의 코드를 반복문을 통해 간소화 한다면 아래와 같다.

for (let firstDiff of [-1n, 0n, 1n]) {
    for (let secondDiff of [-1n, 0n, 1n]) {
        const first = arr[0] + firstDiff;
        const second = arr[1] + secondDiff;
        const d = second - first;
        const cnt = (firstDiff !== 0n ? 1 : 0) + (secondDiff !== 0n ? 1 : 0);
        dfs(second, 1, d, cnt);
    }
}

 

이제 dfs 함수를 통해 그 다음 인덱스를 검사해본다.

const dfs = (cur, idx, d, cnt) => {
    if (idx === N - 1) {
        answer = Math.min(answer, cnt);
        return;
    }
    const num = arr[idx + 1];
    for (let diff of [-1n, 0n, 1n]) {
        const nextNum = num + diff;
        if (nextNum - cur === d) {
            dfs(nextNum, idx + 1, d, cnt + (diff !== 0n ? 1 : 0));
        }
    }
};

 

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const N = +input[0];
if (N === 1) {
    console.log(0);
    process.exit(0);
}
const arr = input[1].split(' ').map((v) => BigInt(v));

const INF = 1_000_000_001;
let answer = INF;

const dfs = (cur, idx, d, cnt) => {
    if (idx === N - 1) {
        answer = Math.min(answer, cnt);
        return;
    }
    const num = arr[idx + 1];
    for (let diff of [-1n, 0n, 1n]) {
        const nextNum = num + diff;
        if (nextNum - cur === d) {
            dfs(nextNum, idx + 1, d, cnt + (diff !== 0n ? 1 : 0));
        }
    }
};


for (let firstDiff of [-1n, 0n, 1n]) {
    for (let secondDiff of [-1n, 0n, 1n]) {
        const first = arr[0] + firstDiff;
        const second = arr[1] + secondDiff;
        const d = second - first;
        const cnt = (firstDiff !== 0n ? 1 : 0) + (secondDiff !== 0n ? 1 : 0);
        dfs(second, 1, d, cnt);
    }
}

console.log(answer === INF ? -1 : answer);