[백준] 17088번 등차수열 변환 문제 풀어보기

1. 문제

www.acmicpc.net/problem/17088

문제는 위 링크에 들어가면 확인할 수 있다.

---

2. 풀이

이 문제는 등차수열의 성질을 활용하여 푸는 문제인데, 첫째항과 공차를 결정하여서 풀 수 있다.

 

가능한 첫째항은 a1, a1+1, a1-1 이렇게 세 가지가 가능하고, 마찬가지로 둘째항은 a2, a2+1, a2-1 이렇게 세 가지가 가능하다. 

 

그러면 총 3*3= 9가지의 경우의 수가 존재하고 첫째항과 공차가 결정되므로 모든 항에 대해서 가능한지 결정해보면 된다. 

3. 코드 

따라서 이를 코드로 구현한 것은 아래와 같다.

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        if (n == 1) {
            System.out.println(0);
            System.exit(0);
        }
        int ans=-1;
        for(int c1=-1;c1<=1; c1++ ){
            for(int c2=-1; c2<=1; c2++){
                int change=0;
                if (c1!=0) change++;
                if (c2!=0) change++;
                int a1=a[0]+c1;
                int d=a[1]+c2-a1;
                boolean ok=true;
                int cur=a1+d;
                for(int i=2; i<n; i++){
                    cur+=d;
                    if (a[i]==cur) continue;
                    else if (a[i]+1==cur || a[i]-1==cur){
                        change++;
                    }
                    else{
                        ok=false;
                        break;
                    }
                }
                if (ok) {
                    if (ans == -1 || ans > change) {
                        ans = change;
                    }
                }
            }
        }
         System.out.println(ans);
    }
}

 

여기서 change란 숫자를 변경하는 횟수를 뜻한다. 1 차이가 나면 1번 변경하면 가능하기 때문에 change를 1 증가시키는 것이다.