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

https://www.acmicpc.net/problem/17088

17088번: 등차수열 변환

Problem

• 크기가 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 ≤ 10^5)이 주어진다. 둘째 줄에는 B1, B2, ..., BN(1 ≤ Bi ≤ 10^9)이 주어진다.

SOL

단순히 구현을 한다면, 모든 값에 +-1,+0씩 해보면서, 등차수열이 성립하는지 확인하면 된다.

하지만, 그렇게 된다면, 경우의 수가 3가지이고, N의 크기가 10,000이기 때문에, 3^10,000, TL이 확실하게 발생한다.

N= 1,2 일때는 무조건 이건 등차수열을 이룰 수 밖에 없다.

 

등차수열은 , A1(첫번째항)과 d(공차)가 정해지면, 등차 수열인지 아닌지 확인 할 수 있다.

등차 수열의 개념(정의)을 여기서..

따라서, 우리는 첫번째항과 공차를 정해주는 작업만 하면 된다!

 

• 첫번째항은 seq[0], seq[0]-1,seq[0]+1 3가지 경우의 수
• 공차를 구해주기 위해, 두번째 항도, seq[1],seq[1]+1,seq[1]-1 3가지 경우의 수

즉, 9가지 경우의 수를 봐주고, 첫번째 항, 공차를 정해준다음, seq[2]항부터, 우리가 정해준 공차로 등차수열이 성립하는지 보면된다.

이때, 우리가 정해준 공차와 +1,-1차이나는건 상관없다. (우리는 모든 항에 +1,-1 연산을 1번 적용할 수 있기 때문이다)

 

#등차 수열 변환 
import sys
input= sys.stdin.readline

N=int(input().rstrip())
seq=list(map(int,input().split()))
#print(seq)
def check(i,j):
    cnt = abs(i)+abs(j)
    arr=[]
    arr.append(seq[1]+j)
    gap = (seq[1]+j) -(seq[0]+i)
    for k in range(2,N):
        if seq[k]==arr[k-2]+gap:
            arr.append(seq[k])
            continue
        if seq[k] -1 == arr[k-2] +gap:
            arr.append(seq[k]-1)
            cnt+=1
            continue
        if seq[k] +1 ==arr[k-2]+gap:
            arr.append(seq[k]+1)
            cnt+=1
            continue
        return False
    return cnt
res=sys.maxsize
if N<3:
    print(0)
    exit()

for i in [-1,0,1]:
    for j in [-1,0,1]:
        #print("i:{},j:{}".format(i,j))
        tmp=check(i,j)
        if not tmp:
            continue
        res=min(res,tmp)

print(res) if res !=sys.maxsize else print(-1)