29번

세로 길이가 2, 가로 길이가 n인 2xn 보드를 2x1 크기의 타일로 보드를 채우는 모든 경우의 수를 구하는 tiling 문제였다.

처음 방법은 재귀를 떠올렸다.

1) 수직 배치시 카운트-1 로 줄어듦
2) 가로 배치시 두 번째 타일도 가로로 붙여야 하므로 카운트-2

n=1 or n=2일 경우, 카운트는 n

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

그러나 실행시간 초과가 떴다. (주의사항에 효율적인 알고리즘 O(N)이 존재한다라고 명시)
재귀 방법은 time complexity가 O(2^n)이기 때문.

따라서 다른 방법을 찾아보다 DP를 적용시키기로 했다. (time complexity : O(n))

int[] dp = new int[num+1];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;

		for(int i=3; i<dp.length; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[num];

위와 같이 작성하니 num=1일 때 ArrayIndexOutOfBoundsException 예외가 발생해서 int[] dp = new int[num+2];로 바꿔주니 모든 테스트가 통과되었다.

참고 사이트
첫 번째 참고 사이트
두 번째 참고 사이트