[JAVA] [SWEA] 4301. 콩 많이 심기

콩을 사랑하는 민석이의 취미는 n*m 크기의 사각형 밭에 콩을 늘어놓는 것이다.

한 칸에 콩 하나씩을 놓을 수 있는데, 2가 싫은 민석이는 콩들 사이의 길이가 2가 되지 않도록 하면서 최대한 많은 콩을 놓으려고 한다.

예를 들어 다음과 같이 콩을 배치할 수 없다.

콩1(x1, y1)과 콩2(x2, y2) 사이의 길이는

이다.

민석이를 도와서 사각형 밭에 최대로 콩을 늘어놓자.

 

이 문제의 경우 처음에는 콩을 배치하고 규칙을 위반하였는지 확인하여하지 않았다면 모든 경우 중에서 규칙을 위반하지 않고 콩이 최대로 많은 경우가 생길 때 콩의 개수를 세는 것이라 생각하였다.

 

하지만 밑에 가로와 세로의 길이가 주어지게 되는데 최대가 각각 1000이며 이경우 1000 * 1000 이 되어 결국 모든 경우를 다 보기엔 엄청난 시간이 소요되게 된다.

 

따라서 생각을 바꾸어 규칙에 맞게 놔두면서 끝까지 갔을 때 콩의 개수를 세면 되지 않을까?

 

라는 생각을 하게 되었고 이를 코드로 옮기어 실행하여 통과하였다.

 

전체 코드는 다음과 같다.

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Solution {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		int M = 0;
		int N = 0;
		boolean[][] flag = null;
        int cnt = 0;
		for(int p=1; p<=T; p++) {
			String[] s = br.readLine().split(" ");
			N = Integer.parseInt(s[0]);
			M = Integer.parseInt(s[1]);
			flag = new boolean[M][N];
			cnt = 0;
			for(int i=M-1; i>=0; i--) {
				for(int j=N-1; j>=0; j--) {
					if( M-i > 2 && N-j > 2 ) {
						if(!flag[i+2][j] && !flag[i][j+2]) {
							flag[i][j] = true;
							cnt++;
						}
					}else if( M-i <= 2 && N-j > 2 ) {
						if(!flag[i][j+2]) {
							flag[i][j] = true;
							cnt++;
						}
					}else if( M-i > 2 && N-j <= 2 ) {
						if(!flag[i+2][j]) {
							flag[i][j] = true;
							cnt++;
						}
					}else if( M-i <= 2 && N-j <= 2 ) {
						flag[i][j] = true;
						cnt++;
					}
				}
			}
			bw.write("#"+p+" "+cnt+"\n");
		}
		br.close();
		bw.close();
	}
}