[백준 1111] IQ Test

[BanApp]

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

python 3

import sys


n = int(sys.stdin.readline())

arr = list(map(int,sys.stdin.readline().split()))

if len(arr) == 1:
    print('A')
    exit(0)

p = 0
for i in arr:
    if i == arr[0]:
        p = p + 1

if p == len(arr) and len(arr) > 1:
    print(arr[0])
    exit(0)

elif p != len(arr) and len(arr) == 2:
    print('A')

elif p != len(arr) and len(arr) > 2:
    tmp = []
    for i in range(1,len(arr)):
        if arr[i-1] == 0:
            pass
        else:
            for j in range(8000):
                r = arr[i-1] * j
                k = arr[i] - r
                f = arr[i] + r
                tmp.append([j, k])
                tmp.append([-j,f])
    x = []

    for i in tmp:
        cnt = 0
        for j in range(0, len(arr) - 1):
            if arr[j] * i[0] + i[1] == arr[j + 1]:
                cnt = cnt + 1
                if [i[0], i[1]] not in x and cnt == len(arr) - 1:
                    x.append([i[0], i[1]])
    if len(x) == 1:
        print(arr[-1] * x[0][0] + x[0][1])
    elif len(x) == 0:
        print('B')
    else:
        print('A')

재밌었던 문제다. 단순히 일차방정식의 해를 브루트포스로 구하는 문제이다.
A,B가 나오는 조건에 맞게 하드코딩만 잘 해주면 된다.
배열이 모두 같은 원소로 이루어지면 arr[0]를 원소가 서로 다르고 배열의 크기가 2일때 A를, 만족하는 해의 값이 없을때는 B를 그렇지 않을때는 방정식의 해를 출력해주면 된다.
이중 반복문을 쓰지 않고 r = arr[i-1] * j, k = arr[i] - r, f = arr[i] + r 이렇게 해주면 O(2*N) 으로 방정식의 해를 모두 구할 수 있다.
근데 a의 범위가 주어지지 않은게 조금 의문이다. 범위를 정수의 최대크기로 놓고 풀면 분명 시간초과가 나지 않을까 싶다.
코로나에 걸리니 알고리즘이 더욱 재미있네요^_^

[jusung-c]

코로나 부작용... ㅋㅋㅋㅋㅋㅋ