[BOJ] 9910: Progress

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

BOJ - Progress

문제 유형: 수학, 다이나믹 프로그래밍, 브루트 포스

문제 난이도: Silver I

시간 제한: 2초

메모리 제한: 1024MB

 

문제

An arithmetic progression is an ascending sequence a of n numbers a1 < a2 < ... < an such that the difference of two consecutive elements is always the same.  Example: The sequence 11 < 21 < 31 < 41 < 51 is an arithmetic progression.  A subsequence of an ascending sequence a of n numbers is a sequence b of m numbers, where m ≤ n, such that every element of b occurs in a.  Example: The sequences 21 < 41 < 51, 11 < 41 and 11 < 21 < 31 < 41 < 51 are three subsequences of the sequence 11 < 21 < 31 < 41 < 51.

Given is an ascending sequence c of k numbers c1 < c2 < ... < ck, the task is to find the length of a longest arithmetic progression that is a subsequence of c.  Note that there may be more than one such longest arithmetic progression, but the length is unique.

Example: Let c be the sequence 1 < 2 < 4 < 5 < 7 < 8 < 9 < 11 < 13 < 14 < 15 < 16.  There are many arithmetic progressions that are subsequences of c, such as 2 < 4, 2 < 8 < 14, and 13 < 14 < 15 < 16.  The longest arithmetic progression that is a subsequence of c is 5 < 7 < 9 < 11 < 13 < 15, and therefore the answer is 6.

You can assume that the length of the sequence, k, is not smaller than 10 and not bigger than 500, and that the elements of the sequence are positive numbers smaller than 100000.

 

등차수열인 가장 긴 부분수열의 길이를 구하시오.

 

입력

The input consists of the following lines:

1. The first line contains an integer indicating the number k of elements of c.
2. The second line consists of the ascending sequence c, where the elements are separated by spaces.

첫 번째줄에 요소의 개수 k가 주어집니다.

두 번째 줄에는 각 요소들이 띄어쓰기로 구분되어 주어집니다.

 

출력

The output contains a single positive integer that indicates the length of the longest arithmetic progression that is a subsequence of c.

 

양의 정수로 최대 부분등차수열의 길이를 구하시오.

 

풀이

dp[i][gap] = arr[i]를 포함하는 공차가 gap인 부분수열의 길이-1로 한다. -1인 이유는 root를 우선 고려하지 않고 시작했다가 최종적으로 1을 더해줄 것이기 때문이다.

 

gap이 sparce한 값일 수 있으므로, unordered_map을 이용했다.

 

LIS문제와 비슷하게 보일 수도 있다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  int k;
  cin >> k;
  vector<int> arr(k);
  for (int i = 0; i < k; ++i) {
    cin >> arr[i];
  }

  int ans = 0;

  vector<unordered_map<int, int>> dp(k);
  for (int i = 1; i < k; ++i) {
    for (int j = 0; j < i; ++j) {
      int gap = arr[i] - arr[j];
      dp[i][gap] = dp[j][gap] + 1;
      ans = max(ans, dp[i][gap]);
    }
  }

  cout << ans + 1 << "\n";

  return 0;
}