[백준] 1111번 - IQ Test / 골드 2 / 파이썬 풀이

문제 링크

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

1111번: IQ Test

 

시간 제한 : 2초

메모리 제한 : 128 MB

 

문제 요약

• 1,2,3,4,5가 주어지고 다음에 오는 수는? => 6.
• 3,6,12,24,48이 주어지고 다음에 오는 수는? => 96.
• 1,4,13,40이 주어지고 다음에 오는 수는? => 121 (앞수*3+1)
• 첫째 줄에 N(<50)이 주어짐 => 주어지는 숫자의 개수
  둘째 줄에 N개의 숫자가 주어짐 (이 숫자들은 모두 -100보다 크거나 같고, 100보다 작거나 같은 정수.)
  
  
• 문제 : 위와 같이 수열이 주어졌을 때 다음에 오는 숫자가 뭔지 맞추는 프로그램 만들기. 이때 모든 답에 대한 규칙은 앞 수 * a + b 형태가 된다.
  
  
• 종료 조건
  - 다음에 오는 숫자가 여러 개일 수 있는 경우는 'A' 출력
  - 다음에 오는 숫자를 구할 수 없는 경우는 'B' 출력

 

입력

예제 입력 4

1
0

예제 입력 5

2
-1 2

예제 입력 7

4
16 -8 4 -2

 

출력

예제 출력 4

A

예제 출력 5

A

예제 출력 7

B

---

풀이

"문제 속에 답이 있다. 앞 수는 array[i]라고 하면, 다음에 오는 수는 array[i+1] 이다."

 다음에 올 수 y = a*x(앞의 수) + b 꼴이라고 문제에서 주어졌다. 그렇다면, a와 b 값을 구하고, 주어진 수열들을 x와 y에 대입하였을 때 모두 성립한다면, 다음에 올 수를 구할 수 있다는 것이다. (하나라도 틀리면 구할 수 없으므로, 'B'를 출력.)

 

 우선 x = array[i], y = array[i+1] 이라고 선언하자.

그런데 a는 위와 같은 일차함수에서 기울기에 해당하므로,

a = (y2 - y1) / (x2 - x1) (x1,x2는 첫번째 x좌표, 두번째 x좌표를 의미하고, y1,y2는 첫번째 y좌표, 두번째 y좌표를 의미.)

  = (array[i+2] - array[i+1]) / (array[i+1] - array[i])

b = y - a*x = array[i+1] - array[i] * a 가 된다.

n = int(input())
data = list(map(int, input().split()))	# 주어진 수열을 저장하는 변수 'data'

if n == 1:  # 숫자가 1개만 주어지면 뒤에 올 수는 모든 숫자가 가능함.
    print('A')
    
elif n == 2:	
    if data[0] == data[1]:	# 숫자가 2개만 주어졌을 때, 두 숫자가 같으면 다음 숫자는 무조건 같음.
        print(data[0])
    else:		# 숫자가 2개만 주어졌을 때, 두 숫자가 다르다면 뒤에 올 수는 모든 숫자가 가능.
        print('A')
       
else:		# 숫자가 3개 이상 주어졌을 때.
    if data[0] == data[1]:		# 기울기의 분모가 0이 되버리는 경우 예외처리.
        a = 0
    else:
        a = (data[2] - data[1]) // (data[1] - data[0])	# 기울기 구하는 식.

    b = data[1] - data[0] * a	# y절편 구하는 식.

    # a와 b를 통해 예측값과 실제값을 비교. 만약 틀리다면 구할 수 없는 경우
    for i in range(n-1):
        expect = data[i] * a + b  # 다음 예측값
        if (data[i + 1] != expect):  # 예측값과 실제가 다르다면
            print('B')
            exit()

    print(data[-1] * a + b)	# 예측값과 실제값이 모두 같다면, 다음 예측 값을 구함. data[-1]은 data 리스트의 가장 마지막 값을 의미.

 

참고

https://velog.io/@ckstn0778/%EB%B0%B1%EC%A4%80-1111%EB%B2%88-IQ-Test-X-1

백준 1111번 - IQ Test(★★★ / XX / 2) : Python