타일 채우기
이번 문제는 점화식 구하는 것 뿐만 아니라 예외를 이해하기 너무 어려웠다.
관련포스트 3개 정도를 보고 나서야 이해가 됐다.
정답은 아래의 점화식이 되겠다.
dp[i]=dp[i-2]*3+(dp[i-4]+dp[i-6]+...)*2
단계별로 완성을 해보면,
dp[i]=0
dp[i]=dp[i-2]*3
:n=2인 타일을 좌측 끝에 붙인다고 생각하면 dp[i-2]의 경우 * 3가지가 된다. dp[i-2]에는 해당 경우에서 고려할 수 있는 예외가 모두 포함되어있다. 하지만 dp[i]에는 왼쪽에 타일이 추가된 경우의 예외만 포함된다.
따라서 타일을 오른쪽에 붙이는 경우를 계산해야만 한다.
dp[i] += (dp[i-4]+dp[i-6]+...)*2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
dp = new int[N + 1];
if (N >=2 && N % 2 == 0) {
dp[0] = 1;
dp[2] = 3;
for (int i = 4; i <= N; i+=2) {
dp[i] = dp[i-2];
for (int j = 0 ; j < i ;j+=2) {
dp[i]+=dp[j]*2;
}
}
}
System.out.println(dp[N]);
br.close();
}
}https://uno-gaebal.tistory.com/11
