[ 백준 ] 2229 / 조 짜기
# Appreciation
/*
* Problem :: 2229 / 조 짜기
*
* Kind :: Dynamic Programming
*
* Insight
* - dp[i][j] = max(i~j 번째 학생들로 조를 만들 때 조가 잘 짜여진 정도)
* + dp[i][j] = max({dp[i][i+1] + dp[i+2][j],
* dp[i][i+2] + dp[i+3][j],
* ...
* })
*
* # 각 구간에서의 최댓갑과 최솟값을 바로 알 수 있으면 좋을 것 같은데...
* 그럼 미리 이를 계산해놓은 전역배열을 만들자!
* -> MX[i][j] = max(i~j 번째 학생들의 점수)
* MN[i][j] = min(i~j 번째 학생들의 점수)
*/
# Code
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <cstring>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N;
int A[1000+1];
int dp[1000+1][1000+1];
int MN[1000+1][1000+1];
int MX[1000+1][1000+1];
// Set up : Functions Declaration
int f(int s, int e);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> N;
for (int i=1; i<=N; i++)
cin >> A[i];
// Process
/* MX[i][j] = max(i~j 번째 학생들의 점수)
* MN[i][j] = min(i~j 번째 학생들의 점수) */
for (int i=1; i<=N; i++) { /* MX, MN 초기화 */
int mx, mn;
mx = mn = A[i];
for (int j=i+1; j<=N; j++) {
mx = max(mx, A[j]);
mn = min(mn, A[j]);
MX[i][j] = mx;
MN[i][j] = mn;
}
}
memset(dp, -1, sizeof(dp));
int ans = f(1, N);
// Control : Output
cout << ans << endl;
}
// Helper Functions
int f(int s, int e)
/* max(s~e 번째 학생들로 조를 만들 때 조가 잘 짜여진 정도) 값을 반환 */
{
if (s == e) return 0;
if (dp[s][e] != -1) return dp[s][e];
dp[s][e] = MX[s][e] - MN[s][e]; /* s~e 번째 학생들로 조를 만들었을 때*/
for (int i=s; i<e; i++) {
/* dp[s][e] = max(dp[s][e], dp[s][i]+dp[i+1][e]) */
dp[s][e] = max(dp[s][e], f(s, i)+f(i+1, e));
}
return dp[s][e];
}
Author And Source
이 문제에 관하여([ 백준 ] 2229 / 조 짜기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gglifer/백준-2229-조-짜기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/*
* Problem :: 2229 / 조 짜기
*
* Kind :: Dynamic Programming
*
* Insight
* - dp[i][j] = max(i~j 번째 학생들로 조를 만들 때 조가 잘 짜여진 정도)
* + dp[i][j] = max({dp[i][i+1] + dp[i+2][j],
* dp[i][i+2] + dp[i+3][j],
* ...
* })
*
* # 각 구간에서의 최댓갑과 최솟값을 바로 알 수 있으면 좋을 것 같은데...
* 그럼 미리 이를 계산해놓은 전역배열을 만들자!
* -> MX[i][j] = max(i~j 번째 학생들의 점수)
* MN[i][j] = min(i~j 번째 학생들의 점수)
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <cstring>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N;
int A[1000+1];
int dp[1000+1][1000+1];
int MN[1000+1][1000+1];
int MX[1000+1][1000+1];
// Set up : Functions Declaration
int f(int s, int e);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> N;
for (int i=1; i<=N; i++)
cin >> A[i];
// Process
/* MX[i][j] = max(i~j 번째 학생들의 점수)
* MN[i][j] = min(i~j 번째 학생들의 점수) */
for (int i=1; i<=N; i++) { /* MX, MN 초기화 */
int mx, mn;
mx = mn = A[i];
for (int j=i+1; j<=N; j++) {
mx = max(mx, A[j]);
mn = min(mn, A[j]);
MX[i][j] = mx;
MN[i][j] = mn;
}
}
memset(dp, -1, sizeof(dp));
int ans = f(1, N);
// Control : Output
cout << ans << endl;
}
// Helper Functions
int f(int s, int e)
/* max(s~e 번째 학생들로 조를 만들 때 조가 잘 짜여진 정도) 값을 반환 */
{
if (s == e) return 0;
if (dp[s][e] != -1) return dp[s][e];
dp[s][e] = MX[s][e] - MN[s][e]; /* s~e 번째 학생들로 조를 만들었을 때*/
for (int i=s; i<e; i++) {
/* dp[s][e] = max(dp[s][e], dp[s][i]+dp[i+1][e]) */
dp[s][e] = max(dp[s][e], f(s, i)+f(i+1, e));
}
return dp[s][e];
}
Author And Source
이 문제에 관하여([ 백준 ] 2229 / 조 짜기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gglifer/백준-2229-조-짜기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)