11/22 블럭 없애기

삼성 코드그라운드에서 제공하는 알고리즘에 관한 개인적인 풀이를 정리했습니다.

아래 사이트에서 직접 풀어보실 수 있습니다.

 

https://www.codeground.org/practice

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

 

이 문제를 풀기 위해 단위시간 별로 외부 블록을 깎아나가는 형식을 사용한다고 했을 때, 다음과 같은 코드를 생각해 볼 수 있다.

#include <iostream>
using namespace std;

int Answer; // 블럭 없애기(시간 초과)

int main(int argc, char** argv)
{
	int T, test_case;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{

		Answer = 0;
		int i, n, blk[100002], change[100002];
		long long sum = 0LL;
		cin >> n;
		for (i = 1; i <= n; i++) {
			cin >> blk[i];
			sum +=(long long)blk[i];
		}
		blk[0] = blk[n+1] = 0;
		for (i = 1; i <= n; i++) {
			cout << blk[i] << " ";
		}
		cout << endl;
		int start = 1, end = n;
		while (sum!=0) {
			for (i = start; i <=end; i++) {
				if (!blk[i]) continue;
				int cmp = min(blk[i - 1], blk[i + 1]);
				if (cmp >= blk[i]) {
					change[i]=blk[i]-1;
					sum -= 1;
				}
				else {
					sum -= blk[i]-cmp;
					change[i] = cmp;
				}
			}

			if (sum == 0) {
				Answer++;
				break;
			}
			for (i = start; i <= end; i++) {
				blk[i] = change[i];
			}

			for (i = start; i <= end; i++) {
				if (blk[i] != 0) {
					start = i;
					break;
				}
			}
			int endtmp=-1;
			for (i = start; i <= end; i++) {
				if (blk[i] != 0) {
					endtmp = i;
				}
			}
			end = endtmp;
			if (end == -1) {
				return -1;
			}
			Answer++;
		}
		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;
}

 

알고리즘은 간단하다. 먼저 각 단위시간마다 각 가로줄에 있는 블록들을 확인한다. 왼쪽 끝이나 오른쪽 끝에 있는 블록은 삭제하고, 나머지 블록들은 자신, 자신의 왼쪽, 자신의 오른쪽 블록 중 가장 낮은 높이로 설정한다. 모든 블록들의 확인이 끝나면 하나의 단위시간이 끝나게 되며, 이 과정을 모든 블록이 사라질 때까지 반복한다. 

 

 

 

이 방법은 직관적으로 생각할 수 있는 방법이지만 큰 N이 입력으로 들어오면 시간제한에 걸리게 된다. 시간 제한에 걸리지 않기 위해서는 다른 방법이 필요한데, 주어진 입력들을 같은 값을 가지는 다른 값으로 치환함으로써 문제를 효과적으로 풀 수 있다. 예를 들어 입력 01810 과 10210의 output은 모두 2로 같다. 이와 같이 모든 이웃한 블록들의 높이 차를 1로 한 뒤에 블록들의 높이 중 최댓값을 찾으면 문제의 답을 구할 수 있다.

 

전체 코드는 다음과 같다.

#include <iostream>
#include <algorithm>
using namespace std;

int Answer;

int main(int argc, char** argv){
	int T, test_case;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{

		Answer = 0;
		int i, n, arr[100002];
		fill(arr, arr + 100002, 0);
		cin >> n;
		for (i = 1; i <= n; i++) {
			cin >> arr[i];
		}

		for (i = 0; i < n; i++) {
			if (arr[i] + 1 < arr[i + 1]) arr[i + 1] = arr[i] + 1;
		}

		for (i = n+1; i > 0; i--) {
			if (arr[i] + 1 < arr[i - 1]) arr[i - 1] = arr[i] + 1;
		}
		cout << "Case #" << test_case + 1 << endl;
		cout << *(max_element(arr, arr + n + 1))<<endl;
	}
	return 0;
}