Lewis's Tech Keep
[백준] 타일 채우기 본문
참고 : www.acmicpc.net/problem/2133
2133번: 타일 채우기
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
www.acmicpc.net
- dp 문제
- 3xn 타일링 문제
- dp[i] =3 *dp[i-2] (i-2번째에서 가능한 모형 3가지 경우) + 2 *dp[i-4]~ dp[0] 까지 ( 각 단계에서 생기는 특수한 경우 2가지)
더보기
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] dp = new int[31];
dp[0] = 1;
dp[2] = 3;
dp[4] = 11;
for (int i = 4; i <= 30; i = i+2) {
dp[i] = 3 * dp[i-2];
for(int j = i-4; j>=0; j = j-2) {
dp[i] += 2*dp[j];
}
}
System.out.println(dp[N]);
}
}
'Java > 알고리즘' 카테고리의 다른 글
[백준] 파티 (0) | 2021.03.28 |
---|---|
[개인 연습] 다익스트라 자바 (0) | 2021.03.28 |
[백준] 2xn 타일링 2 (0) | 2021.03.27 |
[백준] 2048 (easy) (0) | 2021.03.18 |
[백준] 2048(easy) - 실패 (0) | 2021.03.16 |
Comments