백준 11726 2*N 타일링 (Java)

풀이
피보나치 수열과 같은방식으로 가로로 만들 때와 세로로 만들 때의 경우를 합해주면 그다음 번의 경우의 수가 나오는 방식이다.

주의사항
1. Top-down 방식으로 풀 시 memorization을 사용해주어야 시간초과가 나지 않는다.

2. %10007 연산을 마지막에만 해주는 것이 아니라 d[n]을 구할 때마다 해주어야 한다.

• 이유
  나머지연산 공식
  (A+B) % C = (A%C) + (B%C)
  위 공식에 따라 d[n]을 구할때마다 %10007연산을 해주어야 오버플로우가 나지 않는다.
  마지막에만 %10007연산을 해줄 시 중간에 저장되는 값들이 int값을 넘어서므로 오버플로우가 발생한다.

소스코드
1. Top - down 방식
public class Baekjoon11726_Tiling {

      static int[] d;
      static public void main(String args[]){
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();

      d = new int[n+1];

      d[0] = 1;
      d[1] = 1;

      System.out.println(tiling(n));
    }
      static public int tiling(int n){
          if(d[n] > 0)
              return d[n];
          else{
              d[n] = (tiling(n-1) + tiling(n-2)) % 10007;
              return d[n];
          }	
       }
	}
    

2. Bottop-up 방식
   public class Baekjoon11726_Tiling {

   	static public void main(String args[]){
   		Scanner sc = new Scanner(System.in);
           int n = sc.nextInt();
   
      		int[] d = new int[n+1];
   
       	d[0] = 1;
       	d[1] = 1;
   
       	//나머지
       	if(n>=2){
           	for(int i = 2; i <= n; i++){
               	d[i] = (d[i-1] + d[i-2]) % 10007;
           	}
       	}
       	System.out.println(d[n]);
   	}
    }