Boj 7267 c++ 이탈리아어 문제

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

 

 

문제

8개의 수영장 레인이 있다. N명이 사람의 수영 실력이 주어질 때, N명의 사람들을 a 명 이상 b 명 이하로 이루어진 팀으로 나눌 수 있다. 팀 내에서 사람들 간의 실력 차이가 최소화되도록 팀을 구성할 때, 차이의 최솟값을 구하시오.

 

 

 

접근 & 풀이

우선 각 사람들을 정렬 시켜 놓은 후, 연속한 a ~ b명을 고르는 것이 유리하다는 것을 알 수 있다.

그리고 앞서 구성한 팀의 최소 차이와 현재 팀의 최소 차이 중에서 큰 것을 참조하고, 현재 dp 값의 최솟값을 유지해야 하기 때문에

초기값을 inf로 둔 후, min과 max를 동시에 사용하여 점화식을 구성해주면 된다.

 

정답코드

#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define inf 99999999999
using namespace std;
int dp[500001], arr[500001];
int32_t main() {
	fastio
	int N, a, b;
	cin >> N >> a >> b;
	
	for(int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	for(int i = 0; i <= N; i++) {
		dp[i] = inf;
	}
	dp[0] = 0;
	for(int i = 1; i <= N; i++) {
		for(int j = a; j <= b; j++) {
			if(i < j)continue;
			if(dp[i-j] == inf)continue;
			dp[i] = min(max(arr[i] - arr[i-j+1], dp[i-j]), dp[i]);
		}
	}
	cout << dp[N];
}