3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//N 입력 받기
int n = Integer.parseInt(br.readLine());
//N이 1일 경우
if(n==1){
System.out.println(0);
return;
}
//N이 2 이상일 경우
//0칸을 채우는 경우의 수는 1
int[] dp=new int[n+1];
dp[0]=1;
for(int i=2; i<dp.length; i++){
//3*2칸을 채우는 총 3가지 경우의 수를 (i-2)칸의 경우의 수*3을 해서 더해준다.
dp[i]+=dp[i-2]*3;
//3*4칸을 채우는 총 2가지 경우의 수를 (i-4)칸의 경우의 수*2를 해서 더해준다.
//3*6칸을 채우는 총 2가지...
//4, 6, 8, 10, ... 반복
for(int j=4; ; j+=2){
if(i-j>=0)
dp[i]+=dp[i-j]*2;
else
break;
}
}
System.out.println(dp[n]);
}
}
교차해서 쌓는 경우가 4, 6, 8, ...칸마다 2가지 씩이라는 것을 발견 못했었다. 4칸의 경우만 처리해줬다가 틀린 이후 더 있을 수 있는 경우를 생각하다가 알게 됐다.
😁