BOJ 4880 - 다음수

문제

BOJ 4880 - 다음수

세 수가 주어지면 등차수열(AP)인지 등비수열(GP)인지 판별하고 다음 항을 출력하라. 세 수가 모두 0이면 종료.

입력

여러 줄에 세 수가 주어진다. 0 0 0이면 종료.

출력

AP 또는 GP와 다음 항을 출력한다.

예제

풀이

세 수의 연속 차이로 등차/등비를 판별한다.

1. 세 수가 모두 0이면 종료한다
2. a[1] - a[0] == a[2] - a[1]이고 차이가 0이 아니면 등차수열(AP): 공차를 더한다
3. 그 외에는 등비수열(GP): 공비(a[1] / a[0])를 곱한다

핵심 아이디어: 등차와 등비 중 하나임이 보장되므로, 연속 차이의 동일 여부로 O(1)에 판별한다.

코드

#include <iostream>
using namespace std;
int main()
{
  int a[3];
  while (1)
  {
    cin >> a[0] >> a[1] >> a[2];
    if (!a[0] && !a[1] && !a[2])
      break;
    if (a[1] - a[0] == a[2] - a[1] && a[1] - a[0] != 0)
      cout << "AP " << a[1] - a[0] + a[2] << '\n';
    else
      cout << "GP " << a[1] / a[0] * a[2] << '\n';
  }
}

복잡도

• 시간: O(T) (T: 테스트 케이스 수)
• 공간: O(1)