취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 9910번 문제인 Progress이다.
문제는 아래 링크를 확인하자.

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

주어지는 수열의 길이 $k$가 500 이하임에 주목해보자.

문제의 답이 2 이상임은 자명하다. 아무거나 두 개 고르면 되기 때문이다. 그리고 모든 길이 2 이상의 등차수열에는 처음 두 개의 항이 존재하며, 이 두 개의 항이 정해지면 다음으로 와야 하는 수가 항상 정해져있으므로 $O(k^3)$의 시간복잡도로 모든 쌍을 처음 두 항으로 하는 등차수열의 길이를 조사할 수 있게 된다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, mx = 2;
int A[500];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			int gap = A[j] - A[i], nxt = A[j] + gap, len = 2;
			for (int k = j + 1; k < N; k++) {
				if (A[k] == nxt) nxt += gap, len++;
			}
			mx = max(mx, len);
		}
	}

	cout << mx;
}