[Baekjoon 1111] IQ Test

문제

💛Ⅲ [Baekjoon 1111 - IQ Test]

문제 풀이 방법

특정 알고리즘이 없는 브루트 포스 알고리즘 또는 단순 구현문제이다!

1. 주어진 수열의 수가 하나이거나 다른 2개의 값인 경우에는 여러 개의 답이 나올 수 있으므로 ‘A’가 답이 된다.
2. 같은 2개의 값이 주어진 경우에는 다음에 나올 수열은 같은 값이 되므로 답은 수열에서 반복된 숫자가 된다.
3. 3개 이상의 숫자가 주어진 경우에는 앞 수 * a + b 규칙을 찾아야 한다.
   1. 각 수열의 차를 담은 배열 sub를 구한다.
   2. 만약 sub안에 0이 있다면, 같은 숫자가 연속을 나왔다는 의미이다. 이 경우 sub 배열의 1번째 인덱스부터 모두 0이어야만 규칙이 성립하므로 모두 0이라면 답은 수열의 마지막 숫자가 되고, 모두 0이 아니라면 답이 없으므로 ‘B’가 답이 된다.
   3. 0이 없는 경우, sub 배열의 앞 뒤 숫자를 나눈 몫을 담은 div 배열을 구하여 규칙이 존재하는지 확인한다. 만약, div 배열이 모두 같은 값이 나온다면 규칙이 존재하는 것이므로 다음 수열의 숫자를 계산한 값이 답이 되고, 서로 다른 숫자가 존재한다면 ‘B’가 답이 된다.

처음 이 문제를 풀이 했을 때, sub안에 값이 모두 0인지를 검사하는 과정에서 sum(sub[1:0]) == 0 이라는 코드로 풀이했었다. 문제에서 주어진 테스트 케이스를 모두 통과하고, 질문 게시판에 올라는 모든 반례도 통과했는데 자꾸 틀렸습니다가 나와서 어느 로직에 문제가 있을지 고민해봤지만, 결국 반례를 생각해내지 못했다.. 🥲 질문 게시판에 질문을 올리고 약 한달 정도 지났는데 드디어 답글이 달렸다!

모든 값이 0이어야 하는 조건을 sum이 0이다고 풀이해서 틀렸던 것이었다. (지금 생각해보면 정말 말이 안되는 논리…) 저 바보같은 반례를 찾아주신 asdf1705 님 감사합니다 😊

풀이 코드

Python

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

answer = 0
if N == 1 or (N == 2 and arr[0] != arr[1]): # 값이 하나거나 다른 2개의 값인 경우
    answer = 'A'
elif N == 2 and arr[0] == arr[1]:
    answer = arr[0]
else:
    sub = [arr[i+1] - arr[i] for i in range(N-1)]
    if 0 in sub : # 0 일 때 : 같은 숫자가 연속으로 나올 때
        if all(i == 0 for i in sub[1:]): # sum(sub[1:])==0 에서 수정!
            answer = arr[-1]
        else:
            answer = 'B'
    else:
        div = [sub[i+1]/sub[i] for i in range(len(sub)-1)]
        if len(set(div)) != 1 or div[0] != int(div[0]): # 규칙이 없는 경우 또는 정수가 아닌 경우
            answer = 'B'
        else:
            answer = arr[-1] + sub[-1]*int(div[0])
print(answer)