Life Engineering
[BOJ 2133] 타일 채우기 (Java) 본문
https://www.acmicpc.net/problem/2133
import java.util.Scanner;
public class Main {
static int N;
static int[] dp;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
N=sc.nextInt();
dp=new int[N+1];
if (N>1) {
dp[2]=3;
}
if (N>=4 && N%2==0) {
dp[N]=func(N);
}
System.out.println(dp[N]);
}
private static int func(int n) {
if (n<4 || dp[n]!=0) return dp[n];
int sum=3*(func(n-2));
for (int i=4; i<=n-2; i+=2) {
sum+=(func(n-i)*2);
}
dp[n]=sum+2;
return dp[n];
}
}
타일의 가로 길이가 N개일때(a(n))=> (N-2)개는 채워져있고 2개를 채워야 할 경우 (3*(a(n-2))) <2개를 채우는 경우는 3가지>
=>(N-4)개는 채워져있고 4개를 채워야 할 경우 (2*(a(n-4))) 가지 ...
=>(N-6)개는 채워져있고 6개를 채워야 할 경우 (2*(a(n-6))) 가지 ...
=>(N-8)개는 채워져있고 8개를 채워야 할 경우 (2*(a(n-8))) 가지 ...
이런 식이 도출된다는 것을 알 수 있다.
조금 구현이 복잡한데 다른 분(https://kosaf04pyh.tistory.com/236)의 코드를 보니,
dp[31]까지 다 만든 뒤 반복문을 이용해 for문을 4~n까지 돌려줘서 채워주면 된다..재귀로 할 필요 없다.
'Problem Solving' 카테고리의 다른 글
[BOJ 1504] 특정한 최단 경로 (Java) (0) | 2022.03.28 |
---|---|
[프로그래머스] 길 찾기 게임 (Java) (0) | 2022.03.25 |
[프로그래머스] 불량 사용자 (Java) (0) | 2022.03.24 |
[BOJ 19238] 스타트 택시 (Java) (0) | 2022.03.23 |
[BOJ 1918] 후위 표기식 (Java) (0) | 2022.03.22 |