[파이썬] 백준 1111번 - IQ Test 풀이

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

티어: 골드 3

 

 

로직

N개의 수들을 lst라는 리스트에 저장합니다.

1. lst가 한 가지의 수로만 이루어졌으며 N이 1이 아닐 때([1, 1, 1, 1] 등)는 lst[0]이 답이 됩니다.

 

2. N이 2보다 작을 때는 A가 답이 됩니다

 

3. [1, 1, 2], [2, 2, 2, 1] 등 같이 같은 수가 반복되다가 또 다른 숫자가 나온다면 B가 답이 됩니다. ([2, 1, 1, 1]같이 반복되는 수가 맨 뒤에 있는 수열은 앞수 * 0 + 1로 표현 가능합니다.)

 

4. 수열의 규칙은 lst[i+1] = lst[i] * a + b 형태로 표현 가능합니다

수열에서 lst[0], lst[1], lst[2]를 이용해

    a * lst[0] + b = lst[1]
    a * lst[1] + b = lst[2]

    a (lst[0] - lst[1]) = lst[1] - lst[2]

 

    a = (lst[2] - lst[1]) / (lst[1] - lst[0])

 

    b = lst[1] - a * lst[0]

 

라는 식을 유도 가능합니다.

 

a, b를 구했으니, 수열의 다른 수들에 대입해 봅니다.

 

5. for문으로 1부터 n-1까지의 i에서, lst[i]가 lst[i-1] * a + b와 일치하지 않을 때가 있는지 검사합니다. 만약 일치하지 않는다면, B가 답이 됩니다.

 

6. A도, B도 아니라면 lst[-1] * a + b가 다음 수로, 답이 됩니다.

 

 

태그에 브루트포스가 왜 있는지 모르겠습니다