[백준/C++/KOI] 25378번 조약돌 풀이

---

모든 조약돌을 가져가는 최대 횟수는 2번 작업을 N번 반복하는 것이다.

그렇다면 1번 작업을 통해서 횟수를 줄여나갈 수 있는데
1번 작업으로 횟수를 줄이려면 인접한 장소의 조약돌을 모두 가져가는 경우일 것이다. (ex: [1, 1] [1 2 1])

예시

5

2, 3, 6, 10, 5

1. 왼쪽에서부터 차례로 모든 조약돌을 오른쪽에 있는 조약돌에서 같은 개수를 가져간다.
2. 첫번째 돌부터 1번작업을 시작하는 경우
   두번째 돌부터 1번작업을 시작하는 경우
   ...
   으로 경우를 나눌 수 있고 그렇게 0이 되는 순간 작업 횟수가 1번 줄어드는 것을 확인할 수 있다.
   음수만큼 가져갈 수 없으니 이 경우 끊어준다.

---

// This Code is written by gloryko fpqpsxh. 2 4 5 5
#include <iostream>
#include <algorithm>
#define MAXN 2501
using namespace std ;
int arr[MAXN], dp[MAXN] ;
int N, answer ;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N ;

    for(int i = 0 ; i < N ; i++)
        cin >> arr[i] ;
    
    for(int i = 0 ; i < N ; i++)
    {
        int remain = arr[i] ;
        dp[i] = max(dp[i], dp[i-1]) ;
        for(int j = i + 1; j < N ; j++)
        {
            remain = arr[j] - remain ;
            if(remain < 0) break ;
            else if(remain == 0) dp[j] = dp[i-1] + 1 ;
        }
    }

    cout << N - dp[N-1] ;
}

---

느낀점:
처음 전혀 감을 잡지 못하고 KOI 답지를 보았는데 행렬곱셈순서 알고리즘이 떠올랐다.

1번 작업을 이어서 해줄 시작점과 끝점을 찾아주면 어떻게 되지 않을까? 하고 생각하게 되었고 점화식을 어거지?로 세우게 되었다.

내 풀이의 time complexity는 (k = 1 ... n) ∑K 로 n(n+1)/2로 빅 오 제곱이다.

사실 dp로 푼게 아니라 거의 브루트포스가 아닌가? 싶은 코드를 짰는데 개선할 수 있다면 알고 싶다.

---

문제: https://www.acmicpc.net/problem/25378

25378번: 조약돌