BOJ 16740 - Arithmetic Progressions

July 6, 2023

최장 등차수열 찾기 문제이다.

일단 정렬을 하고 시작한다.

$dp[l][r]$ 을 $r$ 에서 이전 항이 $l$ 일 때 최장 등차수열이라고 하자.

그럼 $d=a_r-a_l$ 이고 $a_l-d$ 라는 수가 존재하는지를 보고 만약 존재한다면 그 인덱스를 이분탐색 등으로 구해서 그 인덱스를 $j$ 라고 한다면

$dp[l][r] \coloneqq dp[j][l]+1$ 을 해주면 된다.

$j$ 가 존재하지 않는다면 $dp[l][r] \coloneqq 2$ 를 해주면 된다.

You may also enjoy