[SWEA] 4301. 콩 많이 심기 D4 - Simulation

[SWEA] 4301. 콩 많이 심기 D4 - Simulation

제출일 : 2019-09-24

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWLv-yZah48DFAVV

Input

첫째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 10)가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 가로길이 N, 세로길이 M이 주어진다.

(1 ≤ N, M ≤ 1000)

Output

각 테스트 케이스마다 밭에 놓을 수 있는 콩의 최대 개수를 출력하라.

Example

input

1
3 2

output

#1 4    

Solution & Inpression

해당 위치에서 콩을 심을 수 있는지 검사한뒤 콩을 심을 수 있다면 콩을 콩을 심는다.

Code

언어 : JAVA

메모리 : 94,668 kb

실행시간 : 279 ms

import java.util.*;
import java.io.*;

public class Solution {
    static int N, M, cnt;
    static int[][] map;

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            // 가로길이 N, 세로길이 M (1 ≤ N, M ≤ 1000)
            N = sc.nextInt();
            M = sc.nextInt();

            map = new int[M][N];
            cnt = 0;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    solve(i, j);
                }
            }
            System.out.println("#"+tc+" "+cnt);
        }
        sc.close(); // Scanner close
    }

    private static void solve(int i, int j) {

        int[] dx = { -2, 2, 0, 0 };
        int[] dy = { 0, 0, -2, 2 };

        boolean flag = true;

        for (int k = 0; k < 4; k++) {
            int nx = i + dx[k];
            int ny = j + dy[k];

            if (range(nx, ny)) { // 범위 안이고
                if (map[nx][ny] == 1) { // 콩이 심어져 있으면
                    flag = false; // 콩 못심어
                    break;
                }
            }
        }

        if (flag) {
            // System.out.println("i = "+i+", j= "+j);

            map[i][j] = 1;//콩심고
            cnt++; //카운트
        }

    }

    static boolean range(int x, int y) {
        if (0 <= x && x < M && 0 <= y && y < N)
            return true;
        return false;
    }
}