취미로 코딩하기

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

이번에 볼 문제는 백준 15823번 문제인 카드 팩 구매하기이다.
문제는 아래 링크를 확인하자.

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

각 카드마다 해당 카드의 왼쪽에 있는 카드 중 자신과 같은 수가 적힌 가장 가까운 카드의 위치를 기록해둔 배열(아래 구현의 L배열)을 먼저 구해두자. 이는 카드를 앞에서부터 차례대로 읽어가면서 해당 수가 가장 최근에 어떤 인덱스에서 나왔는지를 확인하고 해당 수가 가장 최근에 등장한 인덱스를 현재 카드의 인덱스로 갱신하는 것을 반복하는 것으로 구해낼 수 있다.

위와 같은 배열을 구해두면 "m개의 연속한 카드의 모임을 한 팩으로 구성할 때 구입할 수 있는 카드팩의 최댓값"을 구하는 작은 문제를 투포인터 기법을 이용해 구해낼 수 있게 된다. 가장 왼쪽에서 찾을 수 있는 m개의 연속한 카드의 모임을 팩으로 구성해나가는 그리디한 방식으로 작은 문제를 해결할 수 있음을 관찰하자.

한편, 위 작은 문제의 답은 m이 커질 때 단조감소함을 알 수 있다. 따라서 m의 범위를 1 이상 N 이하로 잡아 이진 탐색(binary search)를 하는 것으로 본 문제를 해결할 수 있음을 알 수 있다.

위의 내용을 잘 구현해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, M;
int old[500001];
int L[100001]; // i의 왼쪽에 있는 카드들 중 가장 오른쪽에 있는, i에 있는 카드와 같은 카드의 위치

int func(int m) {
	int ret = 0, l = 1, r = 1;
	while (r <= N) {
		l = max(l, L[r] + 1);
		if (r - l + 1 == m) ret++, l = r + 1;
		r++;
	}

	return ret;
}

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		L[i] = old[x];
		old[x] = i;
	}

	int ansL = 1, ansR = N;
	while (ansL < ansR) {
		int mid = (ansL + ansR) / 2 + 1;
		if (func(mid) < M) ansR = mid - 1;
		else ansL = mid;
	}

	cout << ansL;
}