[백준] 17088번 등차수열 변환 - Python / 알고리즘 중급 2/3 - 브루트 포스 - 문제

ByungJik_Oh·2025년 7월 23일

[Baekjoon Online Judge]

목록 보기

210/244

💡 문제

크기가 N인 수열 A = [A $_1$ , A $_2$ , ..., A $_N$ ]이 있을 때, 모든 1 ≤ i < N에 대해서, A $_{i+1}$ -A $_i$ 가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]은 등차수열이 아니다.

수열 B = [B $_1$ , B $_2$ , ..., B $_N$ ]을 등차수열로 변환하려고 한다. 각각의 수에는 연산을 최대 한 번 적용할 수 있다. 연산은 두 가지가 있는데, 1을 더하거나 1을 빼는 것이다. 수열 B를 등차수열로 변환하기 위해 필요한 연산 횟수의 최솟값을 구해보자.

입력

첫째 줄에 수열 B의 크기 N(1 ≤ N ≤ 10 $^5$ )이 주어진다. 둘째 줄에는 B $_1$ , B $_2$ , ..., B $_N$ (1 ≤ B $_i$ ≤ 10 $^9$ )이 주어진다.

출력

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

💭 접근

등차수열을 판단하기 위해서는 가장 처음 두 수의 차가 뒤에 올 숫자들을 결정하게 된다.

따라서 처음 두 수에 적용할 연산을 먼저 적용한 뒤, 이 두 수의 차를 이용하여 뒤따르는 숫자들에 적용할 연산을 정하면 된다.

먼저 아래와 같이 처음 두 수에 적용할 연산의 조합을 저장한다.

db = [
    [-1, -1, 2],
    [-1, 0, 1],
    [-1, 1, 2],
    [0, -1, 1],
    [0, 0, 0],
    [0, 1, 1],
    [1, -1, 2],
    [1, 0, 1],
    [1, 1, 2]
]

db의 각 원소의 첫번째 원소는 첫번째 숫자에 적용할 연산, 두번째 원소는 두번째 숫자에 적용할 연산, 마지막 원소는 처음 두 수에 적용한 연산의 횟수이다.

이제 이렇게 처음 두 수에 연산을 적용하였다면 두 수의 차를 구해 뒤따르는 숫자에 적용할 연산을 결정하며 나아간 뒤, 등차수열을 완성하였다면 연산 횟수 (정답)을 최솟값으로 갱신해주면 된다.

📒 코드

n = int(input())
b = list(map(int, input().split()))

if n <= 2:
    print(0)
else:
    db = [
        [-1, -1, 2],
        [-1, 0, 1],
        [-1, 1, 2],
        [0, -1, 1],
        [0, 0, 0],
        [0, 1, 1],
        [1, -1, 2],
        [1, 0, 1],
        [1, 1, 2]
    ]

    ans = n
    ans_flag = False
    for d1, d2, cnt in db:
        tmp_b = b[:]

        tmp_b[0] += d1
        tmp_b[1] += d2
        tmp_ans = cnt

        diff = tmp_b[1] - tmp_b[0]
        for i in range(2, n):
            if (tmp_b[i] - 1) - tmp_b[i - 1] == diff:
                tmp_b[i] -= 1
                tmp_ans += 1
            elif tmp_b[i] - tmp_b[i - 1] == diff:
                continue
            elif (tmp_b[i] + 1) - tmp_b[i - 1] == diff:
                tmp_b[i] += 1
                tmp_ans += 1
            else:
                break
        else:
            ans_flag = True
            ans = min(ans, tmp_ans)

    if ans_flag:
        print(ans)
    else:
        print(-1)