[백준][파이썬]
문제 번호 : 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
- 입력된 수가 2개 이하이면 항상 등차수열이 된다. 그런 경우 연산을 0번 진행하기 때문에
print(0)를 하고 프로그램을 종료한다. - 입력된 수가 3개 이상인 경우를 생각해보면 A1, A2, A3 에 각각 연산을 한 후 A1 - A2 과 A2-A3가 같아지는 경우들만 cases에 추가해준다. 이 때 연산 횟수는 -1, 1 은 각 한 번씩, 0은 연산을 하지 않은 것으로 생각하기 위해서 절대값을 취해줬다.
cases에 추가된 경우들에서 4번 째 수부터 첫 번째 수와 차를 이용해서 구한 예상값과 차이가 1보다 크면 등차수열이 만들어질 수 없다.- 예상값과 차이가 1이면 연산횟수를 1 더해주고 0이면 그냥 넘어간다. 마지막 수까지 예상값과 차이가 1 이하이면
answer에cnt의 최소값을 넣어준다. - 처음에
answer = n + 1로 정의했기 때문에 등차수열을 만들 수 있는case가 존재하지 않으면answer > n이기 때문에 -1을 출력하도록 한다.
'프로그래밍 > BAEKJOON' 카테고리의 다른 글
| [백준][파이썬] 2210번 - 숫자판 점프 (0) | 2021.08.21 |
|---|---|
| [백준][파이썬] 15686번 - 치킨 배달 (0) | 2021.08.21 |
| [백준][파이썬] 15683번 감시 (0) | 2021.07.24 |
| [백준][파이썬] 16637번 괄호 추가하기 (0) | 2021.07.19 |
| [백준][파이썬] 16943번 숫자 재배치 (0) | 2021.07.19 |
