[ 백준 / 6178 번 ] Bronze I Lake Making - Solved by Java

www.acmicpc.net/problem/6178

6178번: Lake Making

문제

Farmer John wants his cows to help him make a lake. He has mapped the pasture where he wants to build the lake by creating a R (3 <= R <= 100) row by C (3 <= C <= 100) column grid of six foot by six foot squares and then by determining the average elevation (10 <= elev_rc <= 5000) in inches for each square.

Additionally, he has trained the cows in "stomp digging". The burly bovines travel in a herd that just exactly covers a 3x3 grid of squares to a grid whose upper left coordinate is R_s,C_s (1 <= R_s <= R-2; 1 <= C_s <= C-2). The cows then stomp the ground to push it down D_s (1 <= D_s <= 40) inches. The cows are quite meticulous; the cows at lower elevations will not commence stomping until the rest of the herd has joined them. Thus, not all the 3x3 grid is necessarily stomped (or perhaps some part is stomped less than some other part).

Given an initial set of elevations, an ordered set of N (1 <= N <= 20000) stomp digging instructions, and an elevation E (0 <= E <= 5000) for the lake's final water level, determine the volume of water (in cubic inches) that the lake will hold. It is guaranteed that the answer will not exceed 2,000,000,000.  Presume that the edge of the lake contains barriers so that water can not spill over the border.

Consider a small 4 x 6 pasture to be turned into a lake. Its initial elevations (annotated with row/column numbers) are:

column 1 2 3 4 5 6 row 1: 28 25 20 32 34 36 row 2: 27 25 20 20 30 34 row 3: 24 20 20 20 20 30 row 4: 20 20 14 14 20 20

Interpreting the map, we see a hill in the upper right corner that rises to elevation 36; a small hill also rises to elevation 28 in the upper left corner. The middle of row 4 has a slight depression. After the cow-stomping instruction "1 4 4", the pasture has these elevations:

1 2 3 4 5 6 row 1: 28 25 20 32 32 32 row 2: 27 25 20 20 30 32 row 3: 24 20 20 20 20 30 row 4: 20 20 14 14 20 20

Note that only three squares were stomped down. The other six sets of cows were waiting for the stompers to get to their level, which never happened.  After stomping down the upper left corner with this instruction "1 1 10", the pasture looks like this:

1 2 3 4 5 6 row 1: 18 18 18 32 32 32 row 2: 18 18 18 20 30 32 row 3: 18 18 18 20 20 30 row 4: 20 20 14 14 20 20

If the final elevation of the lake is to be 22 inches, the pasture has these depths:

1 2 3 4 5 6 row 1: 4 4 4 -- -- -- row 2: 4 4 4 2 -- -- row 3: 4 4 4 2 2 -- row 4: 2 2 8 8 2 2

for a total aggregated depth of 66. Calculate the volume by multiplying by 6 feet x 6 feet = 66 x 72 inches x 72 inches = 342,144 cubic inches.

Write a program to automate this calculation.

농부 존은 그의 소들이 그가 호수를 만드는 것을 도와주기를 원한다. 그는 6피트의 R (3<= R <= 100) 열 격자 (3 <= C <= 100) 열 격자 (3 <= C <= 100) 열 격자)를 만들어 각 정사각형마다 인치로 평균 고도 (10 <= level_rc <= 5000))를 결정함으로써 호수를 건설하고자 하는 목초지도를 만들었다.

게다가, 그는 "스톰프 발굴"을 하는 소들을 훈련시켰다. 벌리 보바인은 정사각형의 3x3 격자를 정확히 덮고 있는 무리 속에서 좌측 상좌표가 R_s, C_s인 격자로 이동한다. (1 <= R_s <= R-2>, 1 <= C_s <= C-2>. 그리고 나서 소들은 땅을 밟아 D_s (1 <= D_s <= 40> 인치) 아래로 밀어 내린다. 그 소들은 꽤 꼼꼼하다. 낮은 고도에 있는 소들은 나머지 무리들이 합류할 때까지 발을 구르기 시작하지 않을 것이다. 따라서 모든 3x3 그리드가 반드시 스탬프(또는 일부 부품이 일부 다른 부품보다 적게 스탬프됨)되는 것은 아니다.

초기 고도 집합에 따라 N(1 <= N <= 20000) 기공 굴착 지침과 호수의 최종 수위 E (0 <= E <= 5000))의 순서가 주어지면 호수가 머무를 물의 부피(입방 인치)를 결정한다. 답은 200억을 넘지 않을 것이 확실하다. 호수 가장자리에는 물이 국경 너머로 흘러가지 않도록 장벽이 있다고 가정해 보자.

작은 4x6 목초지가 호수로 변한다고 생각해라. 초기 표고(행/열 번호로 표시됨)는 다음과 같다.

                      column
                  1  2  3  4  5  6
         row 1:  28 25 20 32 34 36
         row 2:  27 25 20 20 30 34
         row 3:  24 20 20 20 20 30
         row 4:  20 20 14 14 20 20

지도를 해석하면, 오른쪽 위 구석에 36고지까지 올라가는 언덕을 볼 수 있고, 왼쪽 위 구석에 28고지까지 오르는 작은 언덕도 볼 수 있다. 4열 가운데에는 약간의 우울증이 있다. 소몰이 명령 "1 4 4" 이후 목초지에는 다음과 같은 고도가 있다.

                  1  2  3  4  5  6
         row 1:  28 25 20 32 32 32
         row 2:  27 25 20 20 30 32
         row 3:  24 20 20 20 20 30
         row 4:  20 20 14 14 20 20

3개의 사각형만 아래로 굴러떨어졌다는 것을 주목하라. 나머지 여섯 마리의 소들은 기공이 자기 수준에 이르기를 기다리고 있었는데, 그런 일은 결코 일어나지 않았다. 이 지침 "1.1 10"으로 왼쪽 상단 모서리를 밟은 후 목초지는 다음과 같이 보인다.

                  1  2  3  4  5  6
         row 1:  18 18 18 32 32 32
         row 2:  18 18 18 20 30 32
         row 3:  18 18 18 20 20 30
         row 4:  20 20 14 14 20 20

만약 호수의 최종 고도가 22인치라면, 목초지는 다음과 같은 깊이를 가진다.

                  1  2  3  4  5  6
         row 1:   4  4  4 -- -- --
         row 2:   4  4  4  2 -- --
         row 3:   4  4  4  2  2 --
         row 4:   2  2  8  8  2  2

총 집적 깊이 66. 6피트 x 6피트 = 66 x 72인치 x 72인치 = 342,144입방인치를 곱하여 체적을 계산한다.

이 계산을 자동화하는 프로그램을 작성하십시오.

 

풀이 코드 

package newProject;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class LakeMaking {
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		int[][] arr = new int[R][C];
		for(int i =0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ;j< C; j++) {
				arr[i][j]= Integer.parseInt(st.nextToken());
			}
		}
		for(int n = 0; n< N ;n++) {
			st = new StringTokenizer(br.readLine());
			int R_s = Integer.parseInt(st.nextToken())-1;
			int C_s = Integer.parseInt(st.nextToken())-1;
			int D_s = Integer.parseInt(st.nextToken());
			int max = 0; 
			for(int i =R_s; i< R_s+3; i++) {
				for(int j = C_s; j< C_s+3; j++) {
					max = arr[i][j]>max?arr[i][j]:max;
				}
			}
			max-=D_s;
			for(int i =R_s; i< R_s+3; i++) {
				for(int j = C_s; j< C_s+3; j++) {
					arr[i][j] = arr[i][j]>max?max:arr[i][j];
				}
			}
		}
		int depth = 0; 
		for(int i =0; i< R; i++) {
			for(int j =0; j< C ; j++) {
				if(arr[i][j]<E) depth+=E-arr[i][j];
			}
		}
		System.out.println(depth*72*72);
	}
}

ㅊ

영어라 해석하기 어려운 문제... ㅎ

심지어 feet와 inches가 나와서 도데체 뭔소린가 했다. 하지만 그냥 곱해서 출력하란 이야기이다. 

소들은 R_s,C_s 에서 시작하여 3*3 크기로 땅을 누르는데, 누르는 것이므로 max값에서 D_s만큼 뺸 만큼만 눌리게 된다. 

그래서 최종 3*3크기의 값에 최대값이 max-D_s가 되는 방법이다. 

호수의 깊이E가 있으므로 E보다 작은 값들을 통해 depth를 계산하고, 종 출력할 떄는 feet를 inch로 바꾸어 (depth*72*72) 출력한다. 

입력부는 생략하고, 누르는 경우가 나올 떄 부터 설명하면, 

값을 받고, max값을 선언해준다. 

R_s, C_s 부터 3*3을 확인하면서 가장 최대 값을 찾고 

최대값에서 D_s만큼 누른 값이 이제 가장 최대값이 된다. 

그리고 이 최대 값보다 큰 값들은 모두 max값으로 변경시킨다. 

이렇게 N번의 반복을 끝내면, 

depth를 계산한다.

반복문을 돌면서 E인 호수 깊이보다 낮은 것들을 찾아 depth에 그 차이만큼 더해준다.

그리고 출력하면 끝