c언어 16931번 : 겉넓이 구하기 (백준)

#include <stdio.h>

//위 아래는 각각 면적이 n*m 입니다.
//n축, m축이 있다고 하면 n축에서 앞 뒤로 보는 면적과, m축에서 앞 뒤로 보는 면적을 더합니다.
//n축, m축에서 면적을 셀 때는, 이전 칸(없다면 0으로 봄)보다 얼마나 더 높은지를 더해주면 됩니다. 같거나 더 낮다면, 드러난 면적이 없습니다.

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m); //n, m 입력
	int ans[n][m];
	int Ndown[m];
	int Mleft[n];
	
	for(i=0; i<m; i++) Ndown[i] = 0; //처음은 0
	for(i=0; i<n; i++) Mleft[i] = 0; //처음은 0
	
	
	for(i=0; i<n; i++) //입력받기
		for(j=0; j<m; j++) scanf("%d", &ans[i][j]);
	
	
	int a = n*m*2; //위 아래 면적 합친것을 초기값으로

	for(i = 0; i<n; i++) { //n축으로 봤을때의 면적
		for(j=0; j<m; j++) {
			int tmp = ans[i][j] - Ndown[j];
			Ndown[j] = ans[i][j];
			if(tmp>0) a += 2*tmp;
		}
	}
	
	for(i = 0; i<m; i++) { //m축으로 봤을때의 면적
		for(j=0; j<n; j++) {
			int tmp = ans[j][i] - Mleft[j];
			Mleft[j] = ans[j][i];
			if(tmp>0) a += 2*tmp;
		}
	}
	printf("%d", a); //출력
}

 

풀이 : 기하학?

 

면적은

위 아래

n축 에서 봤을 때

m축 에서 봤을 때

로 볼 수 있습니다.

 

위 아래의 면적은  각각 n*m입니다.

n축, m축의 경우엔 직접 세보아야 합니다.

 

직접 세볼 때는 바로 이전의 것보다 현재가 더 높다면, 그 차이를 더해주면 됩니다.

 

 

 

단 위에서 볼 수 있듯이, 어떠한 축에서 한 방향과, 반대 방향에서 본 면적은 같습니다. 즉 한쪽에서 본 것의 면적에 *2을 하면 됩니다.

 

그러므로 n축에서 한 방향으로 봤을 때의 면적에 *2

               m축에서 한 방향으로 봤을 때의 면적에 *2

을 하면 n, m축의 면적들의 개수도  구할 수 있게 되며, 이들을 위 아래서 보는 면적과 더해준 뒤 출력하면 됩니다.

 

https://www.acmicpc.net/problem/16931

16931번: 겉넓이 구하기