(BOJ17088 등차수열 변환

• tags : (algorithm

  No matching post could be found

  - (brute force
• 문제 링크 : https://www.acmicpc.net/problem/17088
• 풀이 링크
  • Python

• 등차수열을 구하는 점에서, 우선 공차(인접한 두 항의 차)가 정해진다면 쉽게 수열을 결정할 수 있다는 점을 생각할 수 있다.
• 여러가지 방법을 고민했는데, 첫번째 항과 두번째 항이 각각 그대로 사용, 1씩 더하거나 뺄 수 있고,
  • 총 9가지 경우의수만 탐색하면 된다.

• 우선 수열 길이가 2이하이거나, 모두 같은 숫자로 이루어진 수열이면 0을 출력한다.

for i in range(-1, 2, 1):
    for j in range(-1, 2, 1):
        tmp = abs(i) + abs(j)
        tmp_seq = seq[::]
        tmp_seq[0] += i
        tmp_seq[1] += j
        diff = tmp_seq[1] - tmp_seq[0]

• 이 부분은 총 9가지 경우의 수를 탐색하는 부분이다.
  • 첫 번째 항과 두 번째 항에 각 연산을 한 뒤 공차를 diff로 선언한다.

for k in range(2, N):
    _diff = tmp_seq[k] - tmp_seq[k - 1]
    if _diff == diff:
        continue
    if _diff == diff + 1:
        tmp_seq[k] -= 1
        tmp += 1
    elif _diff == diff - 1:
        tmp_seq[k] += 1
        tmp += 1
    else:
        break
else:
    if ans == -1 or ans > tmp:
        ans = tmp

• 한번 더 for문을 순회하며, 공차 diff로 수열을 만들 수 있는지 확인한다.
• 각 위치별 값의 차이를 _diff로 선언했고,
  • 공차와의 차이가 1이하일 때 해당하는 연산을 하고,
  • 아니라면 for문을 종료한다.
• 최초 ans값을 -1로 선언했는데, for문이 정상적으로 종료되면
  • ans값이 -1이거나 더 작은 값을 발견하면 갱신해준다.