-
백준(BOJ) 17088번 등차수열 변환알고리즘 풀이/백준(Boj) 2020. 1. 12. 13:47
문제 : https://www.acmicpc.net/problem/17088
17088번: 등차수열 변환
크기가 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]을 등차수열로 변환하려고 한다. 각각의 수에는 연산을 최대 한 번 적용할 수 있다. 연산은 두 가
www.acmicpc.net
풀이 :
모든 경우를 다해 보기에는 N이 10만이기 때문에 3^10만으로 도저히 불가능하다.
따라서 등차수열의 성질을 이용해서 a[0] 과 a [1]만 각각 -1,0,1로 바꿔서 계산해보자
그때 diff 는 a [1] - a [0]이고 등차수열을 했을 때의 값과 a [2] ~ a [n]까지 비교해가면서
cnt를 +해주고 ans와 최소값을 비교하자.
코드 ( C++ )
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 16957번 체스판 위의 공 (0) 2020.01.16 백준(BOJ) 17090번 미로 탈출하기 (0) 2020.01.16 백준(BOJ) 16964번 DFS 스페셜 (0) 2020.01.11 백준(BOJ) 16954번 움직이는 미로 탈출 (0) 2020.01.07 백준(BOJ) 매직 스퀘어로 변경하기 (0) 2020.01.01