[BOJ 25378 // C++] 조약돌

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25378번 문제인 조약돌이다.
문제는 아래 링크를 확인하자.

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

25378번: 조약돌

한 구간 [l,r]에서 돌을 들어내기 위해 작업해야하는 최소 횟수가 r-l보다 작다면, 어떤 인덱스 mid가 있어서 구간 [l,mid]와 [mid+1,r]에서 돌을 들어내기 위해 작업해야하는 최소 횟수가 각각 "mid-l 이하"와 "r - (mid + 1) 이하"가 되게 하는 mid가 존재한다는 점을 관찰하자.

 

따라서, (1)주어진 배열의 각 구간 [l,r] 중 작업해야하는 최소 횟수가 r - l과 같은 구간들을 모두 모으고, (2)배열의 첫 원소부터 마지막 원소까지 이러한 구간들을 가장 많이 사용할 수 있는 방법을 찾아내는 것으로 문제를 해결할 수 있다.

 

[l,r]에서 작업해야하는 최소 횟수가 r-l임을 알았을 때 굳이 [L,r] (L<l) 또는 [l,R] (r<R)을 만족하는 다른 구간들까지 위에 기록할 필요가 없음을 확인하면 더 효율적인 구현을 할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll arr[2500];
int dist[2501];

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

	cin >> N;
	for (int i = 1; i <= N; i++) dist[i] = N;
	for (int i = 0; i < N; i++) cin >> arr[i];

	for (int i = 0; i < N; i++) {
		ll tmp = arr[i];
		for (int k = i + 1; k < N; k++) {
			tmp = arr[k] - tmp;
			if (tmp == 0) {
				dist[k + 1] = min(dist[k + 1], dist[i] + (k - i));
				break;
			}
			if (tmp < 0) break;
		}
		dist[i + 1] = min(dist[i + 1], dist[i] + 1);
	}

	cout << dist[N];
}