취미로 코딩하기

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

이번에 볼 문제는 백준 6988번 문제인 타일 밟기이다.
문제는 아래 링크를 확인하자.

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

주어진 수열에서 찾는 부분수열은 등차수열이라는 특징이 있다. 등차수열의 점화관계를 이용해 DP를 세워 문제를 해결해보자.

구체적으로, i번째 원소 x로 끝나는 공차 d의 부분수열의 합은 x-d라는 값을 가진 j번째 원소로 끝나는 공차 d의 부분수열의 합에 x를 더한 것과 같다. 이와 같은 관계를 이용해 dp를 세워 문제를 해결하자.

"x-d라는 값을 가진 j번째 원소"에 접근을 빠르게 하기 위해 글쓴이는 벡터와 투포인터로 위 내용을 구현하였다. 이와 같은 구현을 하지 않더라도 타일에 적혀있는 자연수의 범위는 100만 이하라는 점을 이용해 수 k가 적혀있는 index를 저장하는 배열 inv를 만들어 문제를 해결할 수 있을 것이다.

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

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int N;
ll arr[3000];
vector<pair<pair<ll, ll>,int>> vec[3000]; // {{간격, 총합}, 콤보}
ll ans = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];

	for (int i = 0; i < N; i++) {
		ll& cur = arr[i];
		auto& vcur = vec[i];
		int vidx = ((int)vcur.size()) - 1, k = i + 1;
		while (-1 < vidx && k < N) {
			if (vcur[vidx].first.first < arr[k] - cur) {
				if (vcur[vidx].second > 2) ans = max(ans, vcur[vidx].first.second);
				vidx--;
			}
			else if (vcur[vidx].first.first > arr[k] - cur) {
				vec[k].emplace_back(make_pair(make_pair(arr[k] - cur, arr[k] + cur), 2));
				k++;
			}
			else {
				vec[k].emplace_back(make_pair(make_pair(arr[k] - cur, vcur[vidx].first.second + arr[k]), vcur[vidx].second + 1));
				vidx--, k++;
			}
		}

		while (-1 < vidx) {
			if (vcur[vidx].second > 2) ans = max(ans, vcur[vidx].first.second);
			vidx--;
		}

		while (k < N) {
			vec[k].emplace_back(make_pair(make_pair(arr[k] - cur, arr[k] + cur), 2));
			k++;
		}
	}

	cout << ans;
}