백준_16931_겉넓이 구하기

풀이 ①

겉넓이를 구할 때,

[앞면의 겉넓이]=[뒷면의 겉넓이],

[왼쪽면의 겉넓이]=[오른쪽면의 겉넓이],

[윗면의 겉넓이]=[아랫면의 겉넓이]=N*M

이기 때문에 앞면, 왼쪽면, 윗면만 구해서 마지막에 *2 하는 방식으로 구현했다.

 

🚨처음에는 각 행별 최대 높이, 각 열별 최대 높이를 더하면 된다고 생각했는데 이렇게 구현하니 정답보다 더 작은 수가 나왔다.

-> 그래서 각 칸마다 계산하는 방식으로 바꾸었더니 정답이 잘 나왔다.

(앞면을 구할 때는 현재칸의 높이 ↔ 윗칸의 높이를 비교하고, 왼쪽면을 구할 때는 현재칸의 높이 ↔ 왼쪽칸의 높이를 비교해서 현재칸이 더 클때만 더했다. 현재칸이 더 작으면 가려지므로.)

 

+ 가장 바깥쪽 블록은 비교하지 않고 다 더해야 하는데 내가 배열의 인덱스를 1부터 시작하도록 설정해서,

arr[0][], arr[][0]에는 어짜피 0이 들어가 있으므로 다 더해진다. (즉, 범위 체크를 안해도 된다!)

#include <iostream>
using namespace std;

int n, m, arr[101][101], ans;

void solve() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (arr[i][j] > arr[i][j - 1]) ans += arr[i][j] - arr[i][j - 1];
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++) {
			if (arr[i][j] > arr[i - 1][j]) ans += arr[i][j] - arr[i - 1][j];
		}
	}
	ans += n * m;
	ans *= 2;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	solve();
	cout << ans;
	return 0;
}

 

풀이 ②

다른 사람들의 풀이를 보니 그냥 모든 칸의 상하좌우를 비교 및 범위체크하는 방식으로 구현한 경우가 많아서, 이렇게도 구현해보았다.

#include<iostream>
#define MAX 101
using namespace std;

int N, M, arr[MAX][MAX], dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };

int solve() {
	int nx, ny, ans = 0, diff;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			for (int k = 0; k < 4; k++) {
				nx = i + dx[k];
				ny = j + dy[k];
				if (nx >= 1 && nx <= N && ny >= 1 && ny <= M) {
					if ((diff = arr[i][j] - arr[nx][ny]) > 0) ans += diff;
				}
				else ans += arr[i][j];
			}
		}
	}
	ans += N * M * 2;
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> arr[i][j];
		}
	}
	cout << solve() << '\n';
	return 0;
}