문제
주어진 수열이 등차수열인지 등비수열인지 판별하고, 다음 항을 출력하라.
입력
첫째 줄에 수열 길이 N, 이후 N줄에 수열의 각 항이 주어진다.
출력
다음 항을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 2 4 6 8 | 10 |
풀이
처음 세 항의 차이로 등차/등비를 판별한다.
- N개의 항을 배열에 저장한다
p[1] - p[0] == p[2] - p[1]이면 등차수열: 마지막 항에 공차를 더한다- 그렇지 않으면 등비수열: 마지막 항에 공비(
p[1] / p[0])를 곱한다
핵심 아이디어: 등차수열과 등비수열 중 하나임이 보장되므로, 연속 차이의 일치 여부만으로 O(1)에 판별할 수 있다.
코드
#include <stdio.h>
main()
{
int n, p[50];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &p[i]);
if (p[1] - p[0] == p[2] - p[1])
printf("%d", p[n - 1] + (p[1] - p[0]));
else
printf("%d", p[n - 1] * (p[1] / p[0]));
}복잡도
- 시간: O(N)
- 공간: O(N)