Boj 2879) 코딩은 예쁘게

문제

백준 2879

설명

목표 인덱스 까지의 차의 부호에 따라 1/0/-1 로 나타내보자. 이때 나타날 수 있는 ...xxx1110001111xxx... 이런 모양은 한번에 처리할 수 없고 부호가 연속된 영역만을 처리하면 두번만에 가능하므로 이것이 최선이다. 그래서 그리디한 전략은 쉽게 떠올릴 수 있다.

제약사항이 작기 때문에 이걸 한번에 하나씩 값을 줄여나가는 구현 방식으로 풀 수도 있다. 하지만 여기서 한번만 더 생각을 해보자. 영역을 둘로 나뉜다는 것은 인덱스의 차를 그래프로 나타낼 때 봉우리가 두번 나타난다는 것이다. 나뉜 봉우리에서도 마찬가지로 적용이 된다. 여기서 문제의 답이 인덱스의 차를 표현한 그래프의 길이의 절반이라는 것을 떠올릴 수 있다.

시간 복잡도

O(\(\mathrm{N}\))

코드

int arr[1001];

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 0; i < n; i++) {
		int a;  cin >> a;
		arr[i] -= a;
	}

	int ans = 0;
	ans += abs(arr[0]) + abs(arr[n-1]);
	
	for (int i = 1; i < n; i++)
		ans += abs(max(0, arr[i]) - max(0, arr[i - 1]));	
	for (int i = 1; i < n; i++)
		ans += abs(max(0, -arr[i]) - max(0, -arr[i - 1]));

	cout << ans / 2;
}