[백준][파이썬] 17088번 등차수열 변환

[백준][파이썬]

문제 번호 : 17088
문제 출처 : https://www.acmicpc.net/problem/17088

---

 

Code

# 등차 수열이려면 첫 번째 차와 두 번째 차가 같은 경우여야 함

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

if n < 3:  # 숫자가 하나 또는 2개면 무조건 등차수열
    print(0)
else:
    diff = []   # 수열에서 한 칸당 차이를 저장
    for i in range(n - 1):
        diff.append(a[i] - a[i + 1])
    if len(set(diff)) == 0: # 차이가 모두 같으면 집합으로 했을 때 값이 하나밖에 없다.
        print(0)
        exit(0)

    op = (-1, 0, 1)     # 연산의 종류
    cases = []
    answer = n + 1      # 최소값을 찾을 거고 값은 연산횟수는 n을 넘어갈 수 없다.
    for i in op:
        for j in op:
            for k in op:
                count = abs(i) + abs(j) + abs(k)
                d1, d2 = diff[0] + i - j, diff[1] + j - k
                if d1 == d2:    # 0번와 1번, 1번와 2번의 차가 같은 경우 cases에 저장
                    cases.append((a[0] + i, d1, count))

    for case in cases:      # 저장된 케이스들만 생각
        start = case[0]
        sub = case[1]
        cnt = case[2]
        if n == 3:          # A3까지 모두 연산을 해봤기 때문에 길이가 3인 경우 답은 cnt일 확률이 높다.
                            # 아닌경우도 있을 듯
            answer = min(answer, cnt)
        for idx in range(3, n):
            tmp = a[idx] - (start - (sub * idx))    # idx 번째의 값이 예상 값보다 1 이상 차이나면
            if abs(tmp) > 1:                        # +-1 연산만으로 등차수열을 만들 수 없다.
                break
            elif abs(tmp) == 1:                     # 값이 1밖에 차이 안나면 +든 -든 연산을 해야된다.
                cnt += 1                            # 뭘할지 정할 필요는 없고 횟수만 세면 된다.
            if idx == n - 1:
                answer = min(answer, cnt)

    print(answer if answer <= n else -1)            # answer가 n+1이면 -1을 출력, 아니면 answer를 출력

Idea

1. 입력된 수가 2개 이하이면 항상 등차수열이 된다. 그런 경우 연산을 0번 진행하기 때문에 print(0)를 하고 프로그램을 종료한다.
2. 입력된 수가 3개 이상인 경우를 생각해보면 A1, A2, A3 에 각각 연산을 한 후 A1 - A2 과 A2-A3가 같아지는 경우들만 cases에 추가해준다. 이 때 연산 횟수는 -1, 1 은 각 한 번씩, 0은 연산을 하지 않은 것으로 생각하기 위해서 절대값을 취해줬다.
3. cases에 추가된 경우들에서 4번 째 수부터 첫 번째 수와 차를 이용해서 구한 예상값과 차이가 1보다 크면 등차수열이 만들어질 수 없다.
4. 예상값과 차이가 1이면 연산횟수를 1 더해주고 0이면 그냥 넘어간다. 마지막 수까지 예상값과 차이가 1 이하이면 answer에 cnt의 최소값을 넣어준다.
5. 처음에 answer = n + 1 로 정의했기 때문에 등차수열을 만들 수 있는 case가 존재하지 않으면 answer > n 이기 때문에 -1을 출력하도록 한다.