문제

[코플릿 - tiling]
[백준 - 2×n 타일링]

---

풀이

타일링 문제는 다이나믹 프로그래밍의 기본이라고 한다.
다이나믹 프로그래밍으로 풀기 위해서는, 이 문제에 규칙을 먼저 파악해야 한다.

규칙

가로 길이가 1일 때부터 하나씩 그려보면, 다음과 같다.

그림에서 알 수 있듯이, 마지막에 오는 타일(초록색)은 2가지 경우밖에 없다.

1. 1x2 크기의 타일
2. 2x1 크기의 타일 2개

즉, 가로가 N일 때, 점화식을 표현해보자면 다음과 같다.

D[N] = D[N-1] + D[N-2]

코드

naive solution

public int tiling(int num) {
   if(num <= 2){
      return num;
   }
   return tiling(num-1) + tiling(num -2);
}

메모이제이션 사용 - O(N)

public int tiling(int num) {
        // num이 1, 2인 경우를 초기화
        ArrayList<Integer> al = new ArrayList<>(Arrays.asList(0,1,2));
        return aux(al, num);
    }

    public int aux(ArrayList<Integer> al, int num){
        if(al.size() > num) return al.get(num); // memo에 존재한다면, 그 값을 가져온다.
        
        al.add(aux(al, num-1) + aux(al, num-2));
        return al.get(num);
    }

• 재귀 사용

---

[참고]
https://blog.naver.com/PostView.naver?blogId=ndb796&logNo=221233586932