알고리즘 풀이/백준(Boj)
백준(BOJ) 17088번 등차수열 변환
100win10
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++ )
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <vector> | |
| using namespace std; | |
| int main() | |
| { | |
| int n; | |
| cin >> n; | |
| vector<int> a(n); | |
| for (int i = 0; i < n; ++i) | |
| cin >> a[i]; | |
| if (n == 1) { | |
| cout << 0 << "\n"; | |
| return 0; | |
| } | |
| int ans = -1; | |
| for(int d1 = -1; d1 <=1; ++d1) | |
| for (int d2 = -1; d2 <= 1; ++d2) | |
| { | |
| int cnt = 0; | |
| if (d1 != 0) cnt += 1; | |
| if (d2 != 0) cnt += 1; | |
| int first = a[0] + d1; | |
| int second = a[1] + d2; | |
| int diff = second - first; | |
| bool ok = false; | |
| int cand = second; | |
| //등차수열의 성질 이용 | |
| for (int i = 2; i < n; ++i) { | |
| cand += diff; | |
| //같으면 그냥 넘어간다 | |
| if (a[i] == cand) continue; | |
| if (a[i] + 1 == cand) | |
| cnt += 1; | |
| else if (a[i] - 1 == cand) | |
| cnt += 1; | |
| // +1이나 -1해서 만들 수 없을때 | |
| else { | |
| ok = true; | |
| break; | |
| } | |
| } | |
| if (!ok) { | |
| if (ans == -1 || cnt < ans) | |
| ans = cnt; | |
| } | |
| } | |
| cout << ans << "\n"; | |
| return 0; | |
| } |
