[Algorithm]Baekjoon 2229번 :: 조 짜기

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

2229번: 조 짜기

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n;
int scores[10001] = { 0 };
int dp[1001][1001] = { 0 };
 
int DFS(int startIndex, int endIndex, int minScore, int maxScore)
{
    int& result = dp[startIndex][endIndex];
 
    if (result != -1) return result;
    if (endIndex == n) return maxScore - minScore;
 
    result = 0;
    int nextScore = scores[endIndex + 1];
 
    if (nextScore < minScore) // 다음사람을 포함
    {
        result = DFS(startIndex, endIndex + 1, nextScore, maxScore);
    }
    else if (nextScore > maxScore)
    {
        result = DFS(startIndex, endIndex + 1, minScore, nextScore);
    }
    else
    {
        result = DFS(startIndex, endIndex + 1, minScore, maxScore);
    }
 
    result = max(result, DFS(endIndex + 1, endIndex + 1, nextScore, nextScore) + maxScore - minScore );
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> scores[i];
    }
 
    memset(dp, -1, sizeof(dp));
 
     cout << DFS(1, 1, scores[1], scores[1]);
}

 

문제 설명이 좀 더 잘되어있으면 좋을 것 같은 문제..

사람들을 막 쪼개서 조를 만든다음, 해당 조의 최대값-최소값들을 다 더했을 때 최대값을 구하는 문제이다.

여기서 조를 짤 때, 반드시 인접한사람끼리만 조를 짤 수 있다. 헷갈리지 말 것.

 

쨌든, 이 문제에서는 매번 두개의 선택지가 주어진다.

 

1. 다음사람을 현재조에 포함시킬것인가?

2. 다음사람을 기준으로 새로운 조를 만들것인가?

 

이 부분을 코드로 표현하면 된다.

나는 dp테이블을 2차원으로 해서 표현했는데, 1차원으로도 가능하더라. 이런식으로 쪼개기문제는 나는 거의 처음접한거같긴한데, 아마 꽤나 흔한 유형일 것 같다. 자주 나올만하다.

 

다음사람을 포함시킬거면 최소값과 최대값갱신을 해줘야하기 때문에, 다음사람의 점수가 현재 최소값,최대값과 비교해서 탐색을 진행하면 된다. 현재최소값보다 작으면 다음 탐색매개변수의 minScore에 넣어주면 되고, 최대값보다 크면 maxScore에, 만약 두 값의 사이라면 그냥 있으나마나한값이니 현재값 그대로 탐색을 진행하면 된다.

 

만약 다음사람부터 새로운조를 만들거면, 일단 현재 조에서의 최대값-최소값 + 새로운 탐색에서의 값을 비교를 통해 result에 업데이트시켜주면 된다.

다음사람부터 새로운 조를만들어서 탐색하는것이기 때문에 DFS(endIndex+1, endIndex+1, nextScore, nextScore)가 된다.

 

시간좀 걸릴줄알았는데 경험이 쌓여서 그런가 생각보다 쉽게 풀었다.