Q2133. 타일 채우기

타일을 저장하며 나아가는 로직

점화식 dp[i] = dp[i-2]*3 + dp[i-4]*2 + ... dp[2]*2 + 2

매 타일마다 new 타일 2개가 추가되므로, +2

dp[i-2] 타일 뒤에 올 수 있는 타일이 3가지 있으므로, +dp[i-2]*3

dp[i-4] 타일 뒤에 올 수 있는 타일은 dp[4]의 new 타일 2개 이므로, +dp[i-4]*2

dp[i-6] 타일 뒤에 올 수 있는 타일은 dp[6]의 new 타일 2개 이므로, +dp[i-6]*2

.

.

.

dp[2] 타일 뒤에 올 수 있는 타일은 dp[i-2]의 new 타일 2개 이므로, +dp[2]*2

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2133 { static long[] array; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int num = Integer.parseInt(st.nextToken()); array = new long[31]; array[2] = 3; if (num%2 == 0) { for (int i = 4; i <= num; i += 2) { for (int j = i-2; j >= 2; j -= 2) { if (j == i-2) { array[i] += array[j]*3; } else { array[i] += array[j]*2; } } array[i] += 2; } System.out.println(array[num]); } else { System.out.println(0); } } }