[백준]#1111 IQ Test

문제

IQ Test의 문제 중에는 공통된 패턴을 찾는 문제가 있다. 수열이 주어졌을 때, 다음 수를 찾는 문제이다.

예를 들어, 1, 2, 3, 4, 5가 주어졌다. 다음 수는 무엇인가? 당연히 답은 6이다. 약간 더 어려운 문제를 보면, 3, 6, 12, 24, 48이 주어졌을 때, 다음 수는 무엇인가? 역시 답은 96이다.

이제 제일 어려운 문제를 보자.

1, 4, 13, 40이 주어졌을 때, 다음 수는 무엇일까? 답은 121이다. 그 이유는 항상 다음 수는 앞 수*3+1이기 때문이다.

은진이는 위의 3문제를 모두 풀지 못했으므로, 자동으로 풀어주는 프로그램을 작성하기로 했다. 항상 모든 답은 구하는 규칙은 앞 수*a + b이다. 그리고, a와 b는 정수이다.

수 N개가 주어졌을 때, 규칙에 맞는 다음 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. 이 수는 모두 절댓값이 100보다 작거나 같은 정수이다.

출력

다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다.

예제 입력 1

4
1 4 13 40

예제 출력 1

121

풀이

이 문제는 dfs(깊이 우선 탐색) 알고리즘을 이용해서 모든 경우의 수를 다 생각해서 풀 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    static int[] arr;
    static int N;
    static HashSet<Integer> ans = new HashSet<>();    //가능한 다음 수 set

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        String[] input = br.readLine().split(" ");
        for(int i=0; i<N; i++)
            arr[i] = Integer.parseInt(input[i]);

        if(N==1)    //하나의 수만 주어지면 다음에 올 수는 무조건 2개 이상
            System.out.println("A");

        else if(N==2) {   //두 수가 주어졌을 때
            if(arr[0]==arr[1])  //두 수가 같으면 다음 수는 무조건 둘과 같은 수
                System.out.println(arr[0]);

            else          //두 수가 다르면 다음 수는 무조건 2개 이상
                System.out.println("A");
        }

        else {
            dfs(0, 0, 0);

            if(ans.size()==0)     //다음에 올 수가 없으면 B
                System.out.println("B");

            else if(ans.size()==1) {
                for(int res : ans)
                    System.out.println(res);
            }

            else      //다음에 올 수가 둘 이상이면 A
                System.out.println("A");
        }
    }

    public static void dfs(int idx, int a, int b) {
        if(idx==N-2) {
            boolean flag = true;

            for(int i=0; i<N-1; i++) {    //마지막에 도달 했을 때 전체 배열에서 만족하는 a,b인지 체크
                if(arr[i]*a + b==arr[i+1]) continue;
                flag = false;
            }

            if(flag)
                ans.add(arr[N-1]*a + b);

            return;
        }

        int pre = arr[idx];
        int temp = arr[idx+1];
        int next = arr[idx+2];

        if(temp-pre==0) {   //temp-pre==0 이면 나눌 수 없으므로 a를 0으로
            dfs(idx+1, 0, temp);
        }

        else {
            int x = (next-temp)/(temp-pre);   //공비
            int y = temp-pre*x;     //공차

            if(next==temp*x+y) {
                dfs(idx+1, x, y);
            }
        }
    }
}