BOJ 28777 Фотографии на память

문제 링크입니다.

문제 요약

$N$개의 정수를 최소 개수의 그룹으로 분할해야 합니다. 그룹을 짓는 방법은 다음의 3가지입니다.

• 1개의 정수
• 차가 20 이하인 두 정수
• 각각의 차가 10 이하인 세 정수

풀이

정수를 크기 순으로 정렬하고 나면 간단한 DP로 문제를 해결할 수 있습니다.

구현 시, 인덱스의 시작 번호를 0이나 1 같은 수로 잡으면 첫 정수를 포함하는 그룹을 지을 때 예외 처리가 귀찮습니다. 인덱스를 3 이상에서 시작해버리고 (딱 계산해서 맞추기 귀찮다면 통 크게 10 정도로 잡아버려도 괜찮아요), 그 앞으로는 그룹 개수를 0으로 맞춰 주면 예외 처리를 피할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

int a[1010], d[1010];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n; for(int i = 4; i <= n+3; i++) cin >> a[i];
	sort(a+4, a+n+4);
	for(int i = 4; i <= n+3; i++){
		d[i] = d[i-1]+1;
		if(a[i]-a[i-1] <= 20) d[i] = min(d[i], d[i-2]+1);
		if(a[i]-a[i-2] <= 10) d[i] = min(d[i], d[i-3]+1);
	}
	cout << d[n+3];
}