17088. 등차수열 반환

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

17088번: 등차수열 변환



 

등차수열의 성질을 이용한 브루트포스

• 등차수열의 n번째 항은 A(n) = A(n-1) + D
• 등차수열의 공차 D는 두번째항에서 첫째항을 빼서 구할 수 있다.
• 가능한 첫째항은 A[0]-1, A[0], A[0]+1 세 가지가 있고, 가능한 둘째항은 A[1]-1,A[1],A[1]+1 세 가지, 총 3*3 = 9가지가 있다.
• 이렇게 9가지의 공차값을 계산해 준 다음, 세번째 항부터 앞서 계산한 공차값을 통해 해당 항의 값과 차이가 +1, -1이 있으면 연산 횟수를 더해준다.

 

 

소스코드 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 
using namespace std;

int n;
int ans = -1;

/*
첫번째항, 두번째항 결정
-> 공차계산
-> 3번째항부터 해당 항값이 공차+0 와 같으면 continue;
->                      공차-1 or 공차+1과 같으면 ans++; an += diff;
-> 최소 cnt = ans


vector<int> a(100000);
int main()
{
    FASTio;
    cin >> n;

    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    
    if(n==1)
    {
        cout << 0 << endl;
        return 0;
    }
    
    for(int d1=-1;d1<=1;d1++)
    {
        for(int d2=-1;d2<=1;d2++)
        {   
            int cnt = 0;
            if(d1!=0) cnt++;
            if(d2!=0) cnt++;

            int a0 = a[0] + d1;
            int a1 = a[1] + d2;
            int diff = a1-a0;
            
            int an = a1 + diff;

            bool isit = true;

            // 3번째 항부터 검사
            for(int i=2;i<n;i++)
            {   
                if(a[i]==an)
                {
                    an +=diff;
                    continue;
                }

                if(a[i]-1==an) cnt++;
                else if(a[i]+1==an) cnt++;
                else
                {
                    isit = false;
                    break;
                }

                an += diff;
            }

            if(isit==true)
            {   
                if(ans==-1 || ans>cnt)
                    ans = cnt;
            }
        }
    }
    
    cout << ans << endl;



    return 0;
}