[ BOJ 백준 2229번 - 조 짜기 ] 해설 및 코드

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

 

 

목적

학생들의 점수가 주어졌을 때, 조가 잘 짜여진 정도의 최댓값을 구하자.

 

접근법

1. 예제는 다음과 같이 조를 나눠야 한다. 이 문제를 DP를 이용하여 구해내자.

 

2. s[i]를 i명으로 조를 짤 때의 조가 잘 짜여진 정도의 최댓값이라고 하자. 예를 들어, s[7]을 구하는 과정을 보자. 초록색 부분은 이전에 구한 값을 이용하고, 파란 부분에 있는 원소들의 최대값과 최솟값을 구해 그 차이를 초록색 부분과 더한다. s[7]은 이러한 방식으로 만들어진 아래 값들 중 최대값을 취하면 된다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
#define N 1001
using namespace std;
 
int n,mx,mn,a[N],s[N];
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    f(i,0,n)cin>>a[i];
    f(i,0,n){
        mx=mn=a[i];
        fr(j,i,0){
            mx=max(mx,a[j]);
            mn=min(mn,a[j]);
            s[i+1]=max(s[i+1],s[j]+mx-mn);
        }
    }
    cout<<s[n];
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.