[BOJ] 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를 출력한다.

풀이방법:

문제에서 찾아야 하는 a와 b를 찾는 것은 연립방정식을 사용한다면 쉽게 찾을 수 있다. 하지만 A, B와 같이 특이 케이스들이 다수 존재하기 때문에 이를 위한 노력이 필요하다. 다음과 같은 케이스들이 존재할 수 있다.

 

1. N이 1인 경우

N이 1인 경우에는 a와 b를 알 수 없기 때문에 다음에 여러 수가 존재할 수 있다. -> A

 

2. N이 2인 경우

N이 2인 경우에도 a와 b를 알 수 없기 때문에 여러 수가 존재할 수 있다.(A) 하지만 첫 두 수가 같다면 a=1, b=0인 특수한 케이스에 해당하기에 마지막 수를 출력한다.

 

3. N이 3 이상인 경우

 N이 3 이상이면 연립방정식을 통해 a와 b를 구할 수 있게 된다. 따라서 첫 세 수를 사용하여 a와 b를 구하도록 한다. 이 때, a와 b를 정수라는 조건이 있기 때문에 소수가 구해지게 된다면 B를 출력하도록 한다.

 a와 b를 정상적으로 구해도 첫 세 수를 통해 구한 값이기 때문에 이 규칙이 주어진 배열 끝까지 동작하는지 확인하는 작업이 필요하다. 규칙이 정상적으로 작동한다면 규칙을 사용하여 다음 수를 출력하고, 그렇지 않다면 B를 출력한다.

N = int(input())
 
numbers = list(map(int, input().split()))
 
if N==1 or (N==2 and numbers[0]!=numbers[1]):
    print("A")
elif N==2 and numbers[0]==numbers[1]:
    print(numbers[1])
else:
    if (numbers[1]-numbers[0])==0:
        sub = [numbers[i+1]-numbers[i] for i in range(N-1)]
        if len(set(sub))==1:
            print(numbers[-1])
        else:
            print("B")
    else:
        a = (numbers[2]-numbers[1])/(numbers[1]-numbers[0])
        if int(a)!=a:
            print("B")
        else:
            b = numbers[1] - a*numbers[0]
            if int(b)!=b:
                print("B")
            else:
                for i in range(N-1):
                    if numbers[i+1] == numbers[i]*a+b:
                        continue
                    else:
                        print("B")
                        break
                else:
                    print(int(numbers[-1]*a + b))
 

문제링크:

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

1111번: IQ Test