Treejin's Note

문제 설명

• 택배가 쌓여 있을 때, 바닥에 닿은 면을 제외하고 바깥과 닿아있는 모든 면에 붉은 페인트를 칠한다.
• 격자의 행 N, 열 M 이 주어진다. ( 1 <= N, M <= 1000)
• N x M 개의 숫자가 주어진다. i번째 줄의 j번째 수는 해당 칸에 쌓인 택배 상자 수이다.
• 어떤 면에도 페인트가 칠해지지 않은 택배 상자의 수 출력하기

문제 풀이

이 문제는 조건부 전체 탐색 문제이다.

전체 탐색을 진행하지만, 조건에 해당하지 않는 값들은 걸러내며 탐색해야 한다.

문제를 읽고 무조건 페인트가 칠해지는 상자는 다음과 같은 조건일 경우이다.

1. 가장 바깥쪽에 위치한 상자는 페인트가 칠해진다.

    N x M으로 상자가 놓여있을 때, 가장 테두리(1행, 1열, N-1행, M-1열)은 바깥과 무조건 닿아있기 때문이다.

2. 가장 위쪽에 위치한 상자는 페인트가 칠해진다.

    1번과 마찬가지로 가장 위에 위치한 상자는 바깥과 닿아있기 때문에 페인트가 칠해지므로,
    3개의 상자가 쌓여있다면 주변에 배치된 상자에 따라 최대 2개까지 페인트로부터 보호받을 수 있다는 것이다.

3. 2에 따라 한 개만 놓여있는 상자는 페인트가 칠해진다.

페인트가 칠해지지 않는 상자는 앞, 뒤, 좌, 우, 위에 상자가 있는 경우 페인트가 칠해지지 않는다.

따라서, 사방에 쌓인 상자 중 제일 낮게 쌓인 상자의 개수가 가운데 상자탑을 보호해줄 수 있는 최대값이다.

문제 풀이 코드

#include <iostream>
#define MAXARR 1001
#define MAXVALUE 9999999999

using namespace std;

int arr[MAXARR][MAXARR];
int dr[] = { -1, 1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };

int main() {
	// 실행 속도 단축
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	// 입력 받기
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> arr[i][j];
		}
	}

	long long cnt = 0;
	for (int i = 1; i < N - 1; ++i) {			// 테두리 영역은 탐색하지 않는다.(1 ~ N-1만 탐색)
		for (int j = 1; j < M - 1; ++j) {
			if (arr[i][j] > 1) {			// 1개 이상일 경우
				int val = arr[i][j] - 1;	// 색칠되는 맨 위의 상자를 제외한다.
				for (int k = 0; k < 4; ++k) {
					// 사방의 상자 중 최소값만큼 가운데 상자가 보호받을 수 있다.
					val = val < arr[i + dr[k]][j + dc[k]] ? val : arr[i + dr[k]][j + dc[k]];
				}
				cnt += val;
			}
		}
	}

	cout << cnt;
	return 0;
}

+ 위의 속도 차이는
ios::sync_with_stdio(false);
cin.tie(NULL);

를 안넣었을 때와 넣었을 때의 차이이다.

위의 코드는 c의 버퍼를 사용하지 않도록 하는 역할을 한다.

해당 코드는 다음에 자세히 알아보자!