백준 1111 - IQ Test
1111번: IQ Test
다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다.
www.acmicpc.net
문제
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를 출력한다.
문제 자체는 굉장히 간단해 보이는데, 생각보다 경우의 수가 꽤 있어서 생각지 못한 경우의 수로 틀리는 경우들이 있었다.
그래서, 문제의 경우의 수들을 먼저 정리해보려고 한다.
※ 경우의 수
1. 단 한개의 수만 나오는 경우 (n이 1일 때)
-> 모두 똑같은 수가 올 수 있다고 생각하고, 다음 수가 여러개인 'A'로 처리한다.
2. 두 개의 수가 나오는 경우 (n이 2일 때)
-> 이 부분이 가장 속기 쉬운 함정이다. 앞 뒤 숫자를 비교해서 같을 경우에는 a가 0이라고 생각하고 앞 수를 그냥 출력, 다르면 다음 수가 뭐가 나올지 모르기 때문에 여러개 올 수 있어서 A 출력
3. 나머지 일반적인 경우
-> 앞 뒤 숫자를 비교해서 같을 경우에는 a가 0이고 b가 앞 수라고 판단할 수 있으므로 입력으로 담아줌
-> 앞 뒤 숫자를 비교해서 다를 경우에는 공식을 사용한다.
공식을 사용하는 경우를 살펴보면
앞 수 * a + b 공식에서 앞 수를 x라고 생각했을 경우 y = ax + b 라는 공식으로 생각할 수 있다.
그렇다면, a는 기울기, b는 y 절편이라고 생각할 수 있게 되는 것이다.
a = (arr[1] - arr[2]) // (arr[0] - arr[1])
b = arr[1] - arr[0] * a
이렇게 표현이 가능하다.
이제 이 경우들을 모두 코드로 처리해보면
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
if n == 1:
print('A')
elif n == 2:
if arr[0] == arr[1]:
print(arr[0])
else:
print('A')
else:
if arr[0] == arr[1]:
a = 0
b = arr[0]
else:
a = (arr[1] - arr[2]) // (arr[0] - arr[1])
b = arr[1] - arr[0] * a
for i in range(n - 1):
if(arr[i + 1] != (arr[i]*a + b)): # 다음 수가 예측 안될 때 B 출력
print('B')
sys.exit(0)
print(arr[-1] * a + b)
이렇게 작성할 수 있고, 마지막 부분에 다음 수가 예측 되지 않는 경우에 'B'를 출력하고 시스템에서 빠져나가주는 방식으로 코드를 완성할 수 있다.
어떤 알고리즘이 있다기 보다 문제 본연의 규칙성과 본연의 모습에 집중해야 하는 문제라 오랜만에 머리를 좀 굴린 듯 하다.