[USACO 2021 December Contest] Problem 2. Air Cownditioning

Level

Bronze

 

 

문제 링크

[백준]        https://www.acmicpc.net/problem/23879

[USACO]    http://www.usaco.org/index.php?page=viewproblem2&cpid=1156

 

 

문제 요약

배열의 연속된 요소들의 값을 한번 올리거나 내리는 경우를 연산 1번으로 볼 때, \(t\) 배열을 \(p\) 배열과 동일하게 만드는데 필요한 최소 연산 횟수 구하기

 

[내 풀이]

해결 방법

우선 \(d[i]=t[i]-p[i]\)를 통해 \(p\) 배열과 \(t\) 배열의 차이를 배열에 저장한다. 값을 올리거나 내리는 것보다 연속된 요소들의 값을 한 번에 올리거나 내리는 경우가 더 효율적이다. 하지만, 어떤 방식으로 범위를 설정할지가 문제이다.

1. \(d[a]>0\),  \(d[b]\leq 0\)
   
   • 이때 \(d[a]\)를 0으로 만들기 위해서 \(d[a]\)와 \(d[b]\)값을 함께 내리게 되면 나중에 \(d[b]\)는 내려진 만큼 다시 올려야 하므로 각각을 내리거나 올리를 연산 횟수와 동일하다.
2. \(d[a]>0\),  \(d[b]>0\)
   • 이때 \(\mid d[a]-d[b] \mid\) 만큼은 둘 다 공통적으로 값을 내려야 하므로 각각의 값을 내릴 때보다 연산 횟수가 적어진다.

따라서, 연속된 양수들의 그룹 또는 연속된 음수들의 그룹을 만들어서 그룹 내 \(\mid d[i] \mid\)의 최솟값만큼 그룹 전체에 값에 변화를 준 후 다시 양수 그룹 또는 음수 그룹으로 나눠주는 방식으로 \(d[i]\)가 모두 0 이 될 때까지 반복한다. 

 

 

시간 복잡도 

사실 잘 모르겠다.. 그런데 확실한 건, 최악의 경우 1 2 3 4... 10000 이 10번 반복되는 경우인데, 이 경우 연산 횟수가 10만 번이다. 

 

코드

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

const int INF=987654321;

int n;
vector<int> d;
long long ans;

void normalize(int, int);

void getSubsequence(int l, int r) {
	int nl, nr;
	for(int i=l; i<=r; ++i) {
		if(d[i]>0) {
			int nl=i; nr=i;
			for(++i;i<=r; ++i) {
				if(d[i]>0) nr=i;
				else break;
			}
			normalize(nl, nr);
			--i;
		}
		if(d[i]<0) {
			nl=i; nr=i;
			for(++i;i<=r; ++i) {
				if(d[i]<0) nr=i;
				else break;
			}
			normalize(nl, nr);
			--i;
		}
	}
}

void normalize(int l, int r) {
	int min=INF;
	for(int i=l; i<=r; ++i)
		if(abs(d[i])<abs(min)) min=d[i];
	for(int i=l; i<=r; ++i) d[i]-=min;
	ans+=abs(min);
	getSubsequence(l, r);
}

int main(void) {
	cin >> n; d=vector<int>(n);
	for(int i=0; i<n; ++i) cin >> d[i];
	for(int i=0; i<n; ++i) {
		int a; cin >> a;
		d[i]=a-d[i];
	}
	getSubsequence(0, n-1);
	cout << ans << '\n';
}

---

[공식 풀이]

해결방법 

공식 풀이를 보고 좀 놀랐다. 우선 d배열을 구하는 것은 동일한데 d[0]와 d[n+1]에 0을 추가해준다. 다음에 d[i]-d[i-1]의 값을 다 더한 후 이를 2로 나눈다. 이 방식이 결국에는 내가 말한 방식을 좀 더 빠르고 간단하게 구현한 것이다. 

• d[i]와 d[i-1]의 차이가 0인 경우에는 두 수는 똑같은 숫자만큼 올리거나 내린다.
• 만약 d[i]와 d[i-1]의 부호가 서로 다르다면 서로 다른 그룹으로 나눠져서 결국 d[i]와 d[i-1]만큼 올리거나 내려야 할 것이다. ex) -2 3의 경우 총 5번의 연산을 해야 한다.
• 만약 둘 다 음수 혹은 양수라면 절댓값이 작은 숫자만큼 값에 변화를 준 후 절대값이 큰 숫자의 경우 둘의 차이만큼 추가로 값의 변화를 주어야 한다. ex) 0 2 5 0의 경우 5번 연산을 해야 하는데 처음에 2만큼 값을 내려준 후 5는 3이 되므로 3만큼 추가로 값을 내려줘야 한다.
• 이때, 2로 나누는 이유는 좌, 우로 변화하는 값만큼 두 번 세어줬기 때문이다. i를 기준으로 볼 때 i-1과 i 그리고 i와 i+1과 총 2번 비교를 한다. ex) 0 2 0의 경우 차이를 다 더하면 4이지만, 실제 연산 횟수는 2이다.

요약을 하자면, 내가 위해서 한 풀이에서는 같은 그룹끼리 나누는 작업을 했는데 여기서는 인접 요소와의 차이만 비교하여 자연스럽게 그룹이 같을 때와 다를 때의 작업을 한 번에 해결해준다.

 

시간 복잡도

d배열을 구한 후 d배열을 한 번만 순회하므로 \(O(N)\)

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> p(N + 1), t(N + 1), d(N + 2);
	for (int i = 1; i <= N; ++i)
		cin >> p[i];
	for (int i = 1; i <= N; ++i)
		cin >> t[i];
	for (int i = 1; i <= N; ++i)
		d[i] = p[i] - t[i];
	int ans = 0;
	for (int i = 0; i <= N; ++i)
		ans += abs(d[i] - d[i + 1]);
	cout << ans / 2;
}