[BOJ 25289] 백준 25289번 - 가장 긴 등차 부분 수열

		제6회 천하제일 코딩대회 예선 풀이
A		[BOJ 25285] 심준의 병역판정검사
B		[BOJ 25286] 11월 11일
C		[BOJ 25287] 순열 정렬
D		[BOJ 25288] 영어 시험
E		[BOJ 25289] 가장 긴 등차 부분 수열

1. 문제

$25289$. 가장 긴 등차 부분 수열 (제6회 천하제일 코딩대회 예선 E번)

백준 25289번 - 가장 긴 등차 부분 수열 (https://www.acmicpc.net/problem/25289)

2. 풀이

현재 숫자 $X$까지의 등차 수열 최대 길이는, 바로 이전 등차 수열(공차: $d$) 항인 $X - d$ 숫자까지의 등차 수열 최대 길이에 영향을 받는다. 따라서 이 문제의 해결 방법으로 dynamic programming을 생각해 볼 수 있다.

공차가 $d$로 정해져있다면, 배열 $A$를 탐색하면서 아래와 같은 규칙에 의해 dp값을 만들 수 있다.

vector<int> dp(101, 0);

if (//A[i]가 등차수열의 첫 번째 항인 경우)
    dp[A[i]] = 1;
else
    dp[A[i]] = dp[A[i] - d] + 1;

따라서, 모든 공차 d($-99\leq d \leq 99$)에 대해서 이를 실행해서 최댓값을 찾으면 정답이다.

3. 채점 결과

4. 회고

대회때 풀이 코드를 작성한 후, 지인과의 코드 리뷰를 통해 필요없는 부분을 삭제하고 통합하여 코드를 개선하였다. 그 결과, 코드가 훨씬 더 깔끔해졌다. (1260B -> 761B)

5. 코드