<Algorithm> 196. 콩 많이심기(SWExpet)

1. 콩 많이심기(SWExpet)

   사용 알고리즘 :  구현

• 규칙을 생각하고 접근을 했는데 매칭이 쉽지 않았다. 그래서 https://sangdo913.tistory.com/115 여기서 접근방법을 보고 풀었다.

• 코드는 간결하지만 상당히 좋은 문제라 생각된다.  접근 방법 + 형태를 코드로 옮길 수 있는지가 이문제의 핵심인 것 같다.

문제에 대한 접근&생각

1. 길이가 2인 콩은 심을 수 없음 -> 위아래 2칸 차이나는 콩은 심을 수 없음 -> 처리 조건!
2. 배열을 탐색하면서 가로와 세로에 해당하는 두칸씩 지워나감 -> 구현 !

코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

import java.util.Scanner;   public class Solution {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int test = sc.nextInt();                  for(int t = 1; t <= test; t++) {             int n = sc.nextInt();             int m = sc.nextInt();             /************************              * 가로 세로 길이가 2가 되는              * 부분들을 지워나가는 방법으로              * 최대 콩 개수를 구한다.              ************************/             int total = n*m;             boolean visited[][] = new boolean[n][m];             for(int i = 0; i < n; i++) {                 for(int j = 0; j < m; j++) {                     if(!visited[i][j]) {                         visited[i][j] = true;                         if(i+2<n&&!visited[i+2][j]) {                             visited[i+2][j] = true;                             total--;                         }                         if(j+2<m&&!visited[i][j+2]) {                             visited[i][j+2] = true;                             total --;                         }                     }                 }             }             System.out.println("#"+t+" "+total);         }     } }   Colored by Color Scripter

cs