[KOI 2008 초등부 3번] 백준 6988 타일 밟기 문제 풀이

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

6988번: 타일 밟기

백준 6988번 문제이자, 정보올림피아드 초등부 2008년도 전국본선 3번문제 타일 밟기 문제이다.

 

문제 분석

타일이 최대 3000개가 주어지고, 타일 번호는 정렬되어 있다.

 

최소 3개 이상 연속된 타일의 숫자 합 중 최대값을 구해야 하고, 연속된 타일이라 함은

타일들 간에 값의 차이가 일정해야 한다는 것이다.

 

등차수열을 이루는 타일 값들의 합이 최대여야 한다는 것

 

타일에 적힌 수는 100만까지 나올 수 있다.

 

알고리즘 설계 및 시간복잡도 분석

타일에 적힌 수는 자연수이므로 1부터 100만의 범위이다.

그러면 타일 간 값의 차이는 1부터 50만 정도가 된다고 볼 수 있다 대충

1 50만 100만1 이렇게 하면 3개가 된다.

 

즉 1 500000 1000001 이렇게 인데, 사실 100만1은 안나오지만, 대충 타일 값 차이가 50만 가까이가

최대값이라고 보면 된다.

 

따라서 타일간 차이값인 diff값을 모두 다 찾아보면서 순회하려면 diff값이 50만개가 될 것이고

 

diff값 별 타일 모두를 다 훑어야 하므로 for-loop 도는 횟수는 50만 * 3천 정도 인데

 

이 값은 15억 정도 되므로, 15초 이상 걸리는 알고리즘 이라고 볼 수있다. 고로 Time Limit Exceed가

자명한 알고리즘이라는 뜻

 

그러면 이 계산량을 줄여야 하는데, N값이 3000이므로 꽤나 작다.

 

3000이라면 //(O(N^2)//)알고리즘을 짜도 돌아간다는 뜻.

 

 

여기서 잘 모르겠어서 아래의 알고리즘 분류를 "보기"를 눌러서 확인해 보았는데

다이나믹 프로그래밍이라고 힌트를 얻었다.

 

그러면 N값을 기준으로 메모이제이션 배열을 활용하면 될 것 같은데, N크기에 맞는 2차원 디피까지는 가능할 것 같다.

 

그렇다면 dp 배열 인덱스에 diff값을 넣을 수는 없다. 메모리 문제도 있고 시간 문제도 있고

 

그래서 //(dp[3000][3000]//)식으로 잡고, //(dp[i][j]//)라 했을 때, //(i//)가 마지막 인덱스고 //(j//)가 직전 인덱스로 해서

 

//(arr[i] - arr[j]//)로 diff값을 구할 수 있으니, 이를 활용해 보기로 했다.

 

dp[i][j] = i번째에서 끝나고, 그 직전에 arr[j]의 값을 갖는 시퀀스 합의 최대값

이라고 정의해보자.

 

처음 3개짜리만 대상으로 dp배열을 모두 전처리 해 놓은 뒤,

모든 dp배열을 돌면서, arr[j], arr[i]를 통해서 다음에 나올 수 있는 값을 구해서, 그 값이 존재하는 지

확인한 뒤, 존재한다면 그 인덱스를 //(k//)라 하고, //(dp[k][i]//)에 //(dp[i][j] + arr[k]//)를 넣는 식으로 구하면 될 듯하다.

 

값이 존재하는지는, 값의 범위가 1부터 100만이므로 배열을 잡기 보다는 c++ stl map같은 자료구조를 쓰면 좋을 것 같다.

배열로 잡는다면 값 자체는 3000개라서 sparse한 배열이 될 것이고, 메모리가 터질 수 있으므로

 

구현 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int arr[3005];
map<int, int> mm;
ll dp[3005][3005]; // dp[i][j] => i번째에서 끝나고, 이전이 j인 시퀀스의 최대 누적합
int main() {
	ll ans = 0;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		arr[i] = tmp;
		mm[tmp] = i;
	}
	for (int i = 1; i < n; i++) {
		int cur = arr[i];
		for (int j = 0; j < i; j++) {
			int prev = arr[j];
			ll next = cur + (cur - prev);
			if (mm.find(next) != mm.end()) {
				int next_idx = mm[next];
				dp[next_idx][i] = cur + prev + next;
				ans = max(ans, dp[next_idx][i]);
			}
		}
	}
	for (int i = 1; i < n; i++) {
		int cur = arr[i];
		for (int j = 0; j < i; j++) {
			if (dp[i][j]) {
				int prev = arr[j];
				ll next = cur + cur - prev;
				if (mm.find(next) != mm.end()) {
					int next_idx = mm[next];
					dp[next_idx][i] = dp[i][j] + next;
					ans = max(ans, dp[next_idx][i]);
				}
			}
		}
	}
	cout << ans << endl;

	return 0;
}