[백준] code.plus(시뮬레이션과 구현,JAVA)16931번, 겉넓이 구하기

문제 링크

2290번: LCD Test

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 정육면체에 겉넓이를 구해야 한다.

 

정육면체의 윗면과 아랫면은 0이 아닌 값의 개수가 해당 면에 겉넓이가 된다.

 

예제입력 2

값이 모두 0이 아니기 때문에 윗면과 아랫면의 겉넓이는 9가 됩니다.

 

윗면가 아랫면이 아닌 다른 면의 겉넓이를 구할 때 사용하는 점화식은

 

탐색하는 방향의 이전 값보다 크면

 = if(arr[i][j] > arr[i][j-1]) ...

 

현재 값 - 이전 값을 결과에 더해주면 됩니다.

arr[i][j] - arr[i][j-1]

 

문제를 해결한 알고리즘의 과정입니다.

1. 정육면체의 정보들을 저장합니다.

2. 윗면과 아랫면과 그 이외에 면들을 점화식을 이용하여 겉넓이를 모두 구한뒤 결과를 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 정육면체의 정보를 저장하였습니다.
• 윗면과 아랫면의 겉넓이를 구합니다.
• 윗면과 아랫면 제외한 겉넓이를 구하는 cal함수를 실행하였습니다.
• 모든 면의 겉넓이의 합을  BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 위에서 설명한 점화식을 이용하여 각 면의 겉넓이를 구하였습니다.

 

import java.util.*;
import java.io.*;
public class Main {
	static int N,M,result = 0;
	static int[][] arr;		//정육면체 정보 저장
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N+2][M+2];
        	//정육면체 정보 저장
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j=1;j<=M;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(arr[i][j]!=0)	//윗면 아랫면 겉넓이 구하기
					result+=2;
			}
		}
		cal();		//윗면, 아랫면 이외의 면 겉넓이 구하기 함수 실행
		bw.write(result + "\n");		//모든 겉넓이의 합 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//윗면, 아랫면 이외의 면 겉넓이 구하기 함수 실행
	static void cal() {
    		//윗면을 중심으로 남쪽 면
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=M;j++) {
				if(arr[i][j]> arr[i][j-1]) 
					result = result +  (arr[i][j] - arr[i][j-1]);
			}
		}
        	//윗면을 중심으로 서쪽 면
		for(int i=1;i<=M;i++) {
			for(int j=1;j<=N;j++) {
				if(arr[j][i] > arr[j-1][i])
					result = result + (arr[j][i] - arr[j-1][i]);
			}
		}
        	//윗면을 중심으로 동쪽 면
		for(int i=N;i>0;i--) {
			for(int j=M;j>0;j--) {
				if(arr[i][j] > arr[i][j+1]) {
					result = result + (arr[i][j] - arr[i][j+1]);
				}
			}
		}
        	//윗면을 중심으로 북쪽 면
		for(int i=M;i>0;i--) {
			for(int j=N;j>0;j--) {
				if(arr[j][i] > arr[j+1][i])
					result = result + (arr[j][i] - arr[j+1][i]);
			}
		}
		return;
	}
}