백준 17088번 등차수열 변환 [C++]

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

 

 

#문제 간단 정리

수학 + 브루트 포스 문

 

#문제 해결 방법

 

등차수열이기 때문에 결국에는 첫항과 마지막항에 +1 0 -1 을 하면 

공차가 각각 정해지는데 이렇게 3*3 경우의 수로 공차가 정해지면 각 항에서 start + 공차 * 인덱스 

를 한 값이 각 벡터에 올바르게 들어 갈 수 있는지 체크해주면 (+1 -1 을 해서 값을 만들 수 있는지 ) 확인해 주면 된다

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int n;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    vector<int> vec(n);
    for (int& x : vec) cin >> x;

    if (n == 1) {
        cout << 0;
        return 0;
    }

    int ans = INT_MAX;

    for (int d1 = -1; d1 <= 1; d1++) {
        for (int d2 = -1; d2 <= 1; d2++) {
    
            int first = vec[0] + d1;
            int second = vec[1] + d2;
     
            int gap = second - first;
   
            int count = 0;
            if (d1 != 0) count++;
            if (d2 != 0) count++;
         
            bool valid = true;
            for (int i = 2; i < n; i++) {
                int expected = first + gap * i;
                int actual = vec[i];
                if (abs(expected - actual) > 1) {
                    valid = false;
                    break;
                }
                if (expected != actual) {
                    count++;
                }
            }
            if (valid) {
                ans = min(ans, count);
            }
        }
    }

    if (ans == INT_MAX) {
        cout << -1;
    }
    else {
        cout << ans;
    }
}