boj 25378 조약돌

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

 

1. 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기
2. 한 장소에서 임의의 개수의 조약돌을 가져가기

조약돌을 가져갈 수 있는 방법은 이렇게 두가지 입니다.

 

"어떤 장소에 조약돌이 더 이상 없는 경우에도 그 장소는 그대로 남아 있어서, 초기에 인접하지 않았던 두 장소가 인접한 것으로 바뀌지 않는다."

그리고 이렇게 조건도 명시되어 있어서 그 자리에 있는 조약돌은 모두 가져가야 되는것을 알 수 있습니다.

 

dp[i]: i번 위치까지 1번 작업을 통해 줄어든 작업의 최대 횟수

우선 최대 작업 횟수는 N번으로,  모두 2번 방법으로 가져가는 경우입니다.

dp를 구할때는 1번 방법만 사용하기 때문에 앞에서 가져간 이후 몇개가 남았는지 유지하는게 중요합니다.

도중에 r = 0이 되었다면 dp[i - 1] + 1으로 갱신하여 횟수를 줄여주도록 합니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 2501
using namespace std;
 
int dp[MAX];
int list[MAX];
int N;
 
void func() {
    for (int i = 1; i <= N; i++) {
        dp[i] = max(dp[i], dp[i - 1]);
        int r = list[i];
        for (int j = i + 1; j <= N; j++) {
            r = list[j] - r;
 
            if (r < 0) break;
            if (!r) dp[j] = max(dp[j], dp[i - 1] + 1);
        }
    }
 
    cout << N - dp[N] << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}