04. 타일 채우기 가능여부 판단 알고리즘

 

##문제## 

 

 

N x M 크기의 바닥에 타일을 붙이려고 합니다.

단, 타일을 왼쪽 그림과 같이 바닥의 테두리에만 붙이고 싶습니다.

붙이려고 하는 타일이 P x 1 크기의 한가지 종류만 사용한다고 할 때,

타일이 겹치는 부분 없이 바닥을 모두 덮을 수 있는지 확인할 수 있는 프로그램을 만들어 주세요!

(단, N과 M은 3 이상이라고 가정합니다.)

 

예를들어, 오른쪽 그림과 같이 6 x 5 크기의 바닥에는

3 x 1 타일로 모두 덮을 수 있고 4 x 1 타일로는 모두 덮을 수 없습니다!

 

example1>

n x m : 5, 6
p : 1, 2, 3

 

example2>

n x m : 102, 100
p : 1, 2, 4, 5, 10, 20, 25, 50, 100

 

example3>

n x m : 500, 500

p : 1, 2, 499

 

힌트 !

모서리에 타일이 배치되는 경우의 수를 빠뜨리지 말고 찾아 보세요!

 

## 풀이 ##

n x m 타일. p x 1 에 대해서,

[n] : (n % p) == 0 의미 한다면 ([n-1]은 n-1 % p == 0),

채울수 있는 조건은 다음과 같은 4가지 조건중 하나일 때.

1) [n-2] && [m]  ==> 의미: ((n-2) % p == 0) && (m % p == 0)

2) [n-1] && [m-1]

3) [n-1] && [m] && [m-2]

4) [n] && [m-2]

5) [m-1] && [n] && [n-2]

 

* Code

private boolean isFillPossible(int nVal, int mVal, int p){
  boolean isPossible = false;
  
  int[] n = new int[3];
  int[] m = new int[3];
  for(int i=0;i<3;i++){
   n[i] = (nVal - i) % p;
   m[i] = (mVal - i) % p;
  }
  
  isPossible = (n[2] == 0 && m[0] == 0) ||
               (n[1]==0 && m[0]==0 && m[2]==0) ||
               (n[0]==0 && n[2]==0 && m[1]==0) ||
               (n[1]==0 && m[1]==0) ||
               (n[0]==0 && m[2]==0 )

    ? true:false;
  return isPossible;
 }

 

 

## 코드 ##

package p1;

 

public class FillWithTile {

         public FillWithTile(){

                  test();

         }

        

         private void test(){

                  int n,m;

                  int p;

                 

                  //1.

                  n=5; m=6;

                  for(p=1;p<=5;p++){

                           if(isFillPossible(n,m,p)){

                                   System.out.print(p+"\t");

                           }

                  }

                  System.out.println("");

                 

                  //2.

                  n=102; m=100;

                  for(p=1;p<=100;p++){

                           if(isFillPossible(n,m,p)){

                                   System.out.print(p+"\t");

                           }

                  }       

                  System.out.println("");

                 

                  //3.

                  n=500; m=500;

                  for(p=1;p<=500;p++){

                           if(isFillPossible(n,m,p)){

                                   System.out.print(p+"\t");

                           }

                  }

         }

        

         private boolean isFillPossible(int nVal, int mVal, int p){

                  boolean isPossible = false;

                 

                  int[] n = new int[3];

                  int[] m = new int[3];

                  for(int i=0;i<3;i++){

                           n[i] = (nVal - i) % p;

                           m[i] = (mVal - i) % p;

                  }

                 

                  isPossible = (    (n[2] == 0 && m[0] == 0) ||

                                             (n[1]==0 && m[0]==0 && m[2]==0) ||

                                             (n[0]==0 && n[2]==0 && m[1]==0) ||

                                             (n[1]==0 && m[1]==0) ||

                                             (n[0]==0 && m[2]==0 )  )

                                   ? true:false;

                  return isPossible;

         }

 

         public static void main(String[] args) {

                  new FillWithTile();

 

         }

 

}

 

 

 

-끝-