[백준(baekjoon) 11726] 2×n 타일링

문제

백준 11726

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

주의 할 것은 출력이 10007을 나눈 나머지 라는 것..!
(이거 안 읽고 계속 틀렸었다…. 문제는 제대로 읽어야 한다..)

해결

처음에는 width 2인 정사각형이 몇 개가 들어가는 지에 따라 경우의 수를 나누어 보았는데, 결과적으로 더 쉬운 패턴을 발견할 수 있었다….

1.n = 1 : answer = 1
2.n = 2 : answer = 2
3.n = 3 : answer = 

결론적으로, 이러한 점화식 형태를 보인다. 그러니 우린 간단하게 점화식을 풀면 됨..!

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.
모두 알테지만, 다시 한번 간단히 정리해보자면

1. Top-down 방식
   
   • 주로 재귀호출을 이용해 푼다.
   • 큰 문제를 작은 문제로 나누고 작은 문제를 이용해 큰 문제를 푸는 방식
   • n 문제를 푸는 것이 목표, func(n)을 호출한다.
   • func(n)안에서는 재귀호출을 하고, 만약 n=바닥(ex:1)인 경우에는 특정 값을 return 한다.
   • func(n)을 호출해 func(바닥)까지 가서 값을 알아내기 때문에 Top-Down이다.
2. Bottom-up 방식
   
   • 핵심은 저장이다. 미리 저장해 둔 값을 이용해 이후 문제를 푼다.
   • 작은 문제부터 큰 문제까지 차례대로 푸는 방식. 주로 for문을 사용해 푼다.
   • 바닥 부터 시작해 n의 값을 알아내기 때문에 Bottom-Up이다.

구현 java

공통적인 것

• tile에 값들을 저장한다는 것

1. Top-Down 방식

1.import java.util.*;
2.
3.public class Main {
4.    static long[] tile;
5.    public static void main (String[] args) {
6.        Scanner sc  = new Scanner(System.in);
7.
8.        int n = sc.nextInt();
9.        tile = new long[n+1];
10.
11.        tile[1] = 1;
12.        if (n > 1) tile[2] = 2;
13.
14.        System.out.println(goTo(n));
15.    }
16.
17.    public static long goTo (int n) {
18.        if (n==1) return 1;
19.        if (n==2) return 2;
20.
21.        long a = tile[n-1] > 0 ? tile[n-1] : goTo(n-1);
22.        long b = tile[n-2] > 0 ? tile[n-2] : goTo(n-2);
23.        tile[n] = (a + b) % 10007;
24.
25.        return tile[n];
26.    }
27.}

2. Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    static long[] tile;
5.    public static void main (String[] args) {
6.        Scanner sc  = new Scanner(System.in);
7.
8.        int n = sc.nextInt();
9.        tile = new long[n+1];
10.
11.        tile[1] = 1;
12.        if (n > 1) tile[2] = 2;
13.
14.        for (int i = 3; i <= n; i++) tile[i] = (tile[i-2] + tile[i-1]) % 10007;
15.
16.        System.out.println(tile[n]);
17.    }
18.}

결과

1. Top-Down 방식
2. Bottom-Up 방식