백준 20543 JAVA : 폭탄 던지는 태영이

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

20543번: 폭탄 던지는 태영이

---

풀이방법

식을 세워서 접근한다.

 

M = 5일 때 예시

 

1. (i,j의 값을 구하고자 할 때 A 위치의 값을 확인해야 한다.

 

 

2. A 블럭을 기준으로 (i-1, j) , (i, j-1), (i-1, j-1) 블럭도 그려본다. 

 

3. 영역을 색칠하고 영역별로 이름을 매겨 두겠다(b1 ~ b9)

 

4. A~D 블럭의 식을 세워 본다. 우리가 여기서 구하고 싶은 것은 (i, j)의 값인 b9 블럭의 값이다.

 

5. 식을 기반으로 (A-B-C-D) 를 하고, b9에 대해 식을 세운다.

 

6. 그러면 이러한 식이 완성 된다. 이 과정을 코드로 작성해주면 완성

 

7. 주의사항 : long으로 해주어야 함 (범위 초과) 

 

 

소스코드

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

public class Main {
	static int N,M;
	static long[][] map;
	static long[][] bomb; //결과 : 폭탄 개수
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new long[N][N];
		bomb = new long[N][N];
		
		int point = M/2;
		
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = -Long.parseLong(st.nextToken()); //양수로 저장
			}
		}
		
		for (int i = point; i < N - point; i++) {
			for (int j = point; j < N - point; j++) {
				bomb[i][j] = map[i-point][j-point];
				
				if(i-point-1 >= 0) { //B범위 안이면 
					bomb[i][j] -= map[i-point-1][j-point];
				}
				if(j-point-1 >= 0) { //C범위 안이면
					bomb[i][j] -= map[i-point][j-point-1];
				}
				if(i-point-1>=0 && j-point-1 >= 0) { //D범위 안이면
					bomb[i][j] += map[i-point-1][j-point-1];
				}
				
				if(i-M>=0) { //b3의 범위이면
					bomb[i][j] += bomb[i-M][j];
				}
				if(j-M>=0) { //b7의 범위이면
					bomb[i][j] += bomb[i][j-M];
				}
				if(i-M>=0 && j-M>=0) { //b1의 범위이면
					bomb[i][j] -= bomb[i-M][j-M];
				}
				
				
			}
		}
		
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				sb.append(bomb[i][j]).append(" ");
			}
			sb.append("\n");
		}

		
		System.out.println(sb.toString());

	}

}

 

 

결과