[PS] NYPC | 2513. 등차수열

문제

N개의 항을 가진 수열 A가 있다. 각 항에 11을 더하거나 빼는 연산을 수행할 수 있다. 단, 이 연산은 항 하나에 최대 한 번만 적용 가능하다. 즉, A의 i번째 항의 값이 초기에 x로 주어졌다면, 최종적으로 i번째 항의 값은 연산을 수행하지 않은 경우에는 x, 연산을 수행한 경우에는 x+1 혹은 x−1중 하나가 가능하다.

 

최소한의 연산으로 수열 A가 공차 1인 등차수열이 되도록 만드는 프로그램을 작성하라.

 

여기서 공차 1인 등차수열이라 함은, 1 ≤ i < N인 모든 정수 i에 대해, i+1번째 항 A_{i+1​}에서 i번째 항 A_i​를 뺀 값이 A_{i+1}−A_i=1임을 뜻한다.

예시

Example 1.

입력

5 1 3 4 5 5

출력

2

조건

• 첫 줄에 수열의 길이를 나타내는 정수 N이 주어진다. (1≤N≤100000)
• 그다음 줄에 수열의 N개의 항의 초깃값이 공백으로 구분되어 차례대로 주어진다. 이 값은 모두 1 이상 1 000 000 000 이하의 정수다.
• 항상 연산을 적절히 사용하여 공차 1인 등차수열을 만들 수 있는 경우만 입력으로 주어진다.

답

공차가 1인 등차수열로 만드는 것이 목표이기 때문에, 수열은 아래와 같은 형태로 형성된다고 가정할 수 있습니다.

// t: 초항
const goal = [t, t+1, ... , t+N-1]

따라서 주어진 수열의 각 n번째 항에서 n-1 만큼을 뺐을 때 t의 값이 나오도록 해야 합니다.

const inputSubtract = [A_1 - 0, A_2 - 1, ... , A_N - N + 1]
// ===
const goal          = [t,       t,       ... , t          ]

만약 값이 다른 항이 있다면, 그 항이 바로 연산이 필요한 항이 됩니다.

가능한 t의 값은 A_1, A_1 - 1, A_1 + 1 으로 총 세 개입니다.

따라서 각 세 가지 경우에 대해 inputSubstract과 goal에서 값이 다른 항을 찾으면 총 연산 수가 됩니다.

// input
// N : length of sequence
// A[1 - N] : elements

// output
// result (number) : minimum computation
export const ps = (data) => {
    const N = data[0][0];
    const seq = data[1];
    let res = N, cnt = 0;

    for (let i=-1; i<=1; ++i) {
        const expectedInit = seq[0] + i;
        cnt = 0;
        for (let j=0; j<N; ++j) {
            cnt += (seq[j] - j !== expectedInit)? 1 : 0;
        }
        res = Math.min(res, cnt);
    }
    return res;
}

시간 복잡도 : O(n)