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

개요

• 풀이 시간 : 40분
• 시간 제한 : 2초
• 메모리 제한 : 128MB
• 기출 : 백준 1111번 문제
• 링크 : https://www.acmicpc.net/problem/1111

문제

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'를 출력한다. (아 좀 A, B가 문자인걸 표시해주던가...😡😡)

해결방법

이 문제는 그렇게까지 어려운 문제는 아니지만 주의해야할 점이 몇가지 있다.

경우1. N은 50보다 작거나 같은 자연수라는 말은 1~50사이의 값이 될 수 있다는 소리이다. 근데 생각해보면 N이 1일때 규칙을 찾을 수 있을까? 이 경우는 없으니까 A를 출력해야 한다.

경우2. 만약 N이 2이고 서로 숫자가 다를때는? 이경우도 마찬가지로 규칙을 찾을 수 없다. 예를 들어 4, 8이 있는 경우 이는 4씩 더한건지, 2를 곱한건지 알 수 없기 때문이다. 근데 숫자가 서로 같은경우라면 어떨까? 예를 들어 4, 4인 경우는 뒤에도 4가 나올까? 당연히 그럴것이다.

경우3. N이 3보다 큰 경우는 a와 b를 구해야 한다. 근데 a와 b를 어떻게 구해야할지 처음에는 어렵게 생각했다. 근데 문제에 수식에도 나와있듯이 $y = ax + b$ 라고 생각하면 된다. 여기서 x는 array[i], y는 array[i + 1]이라고 생각하면 된다. 이때 a값은 기울기이며 기울기 공식은 (array[i+2] - array[i+1])/(array[i] - array[i-1])이 된다. b는 y절편이며 구하는 방법은 array[i] - array[i-1] * a이다.

이렇게 a와 b를 구한결과를 가지고 전체적으로 for문을 돌면서 패턴을 만족하는지 확인하면 된다. 만약 만족한다면 마지막 값에 다음값을 구해서 출력하면 되고, 아니라면 B를 출력하면 되는 것이다.

Python

20.12.09 처음으로 이문제를 풀고 복습차원에서 21.02.16 다시 이문제를 도전했다. 아 근데 겁나 아쉽네... 거의 정답에 근접했는데

내코드(틀린코드)

n = int(input())
data = list(map(int, input().split()))

if n == 1: 
    print('B')
elif n == 2:
    print('A')
else:
  # 0, 1, 2번을 이용해 a와 b를 구함(이차방정식)
    if (data[0] - data[1] == 0):
        a = 0
    else:
        a = (data[1] - data[2]) // (data[0] - data[1])

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

    # 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)

여기서 n이 1인경우와 2인경우에서 문제가 있었다.

일단 n이 1일때는 B가 아니라 A를 출력해야 한다. 왜냐하면 다음 수가 어떤게 나올지 모르기 때문이다. 아니.. 다음 수를 구할 수 없는것도 맞지 않나? 라고 말할 수도 있겠지만... 곰곰히 생각해보면 다음 수를 구할 수 없다는 의미는 아무래도 a, b가 주어졌지만 예측값과 실제값이 다른 경우를 뜻하는거 같다. (아무래도 여기서 많은 사람들이 틀렸지 않을까?)

두번째 잘못된 경우로는 n이 2일때이다. 나는 단순히 n이 2인 경우 규칙을 찾을 수 없으므로 여러개의 경우가 있겠지라고만 단순히 생각했다. 하지만 잘 생각해보면 첫번째 경우와 두번째 경우 숫자가 같다면? 이러면 당연히 다음 숫자도 똑같을 것이다. 즉 예측할 수 있다는 것이다.

정답코드

위 경우를 토대로 일부만 수정하면 다음과 같다.

...

if n == 1:  # n이 1일때가 A라고?!
    print('A')
elif n == 2:
    if data[0] == data[1]:
        print(data[0])
    else:
        print('A')

...

✍ 글쎄... 문제 자체는 쉬운데 문제가 좀 아쉽네. A와 B가 조금 혼동스럽달까...?