백준 자바 다이나믹 프로그래밍

[백준/JAVA] 14852번 타일 채우기 3

https://www.acmicpc.net/problem/14852 1. 문제 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자. 2. 문제 접근 1) 첫째 줄에 길이 N을 입력받는다. 2) 타일 채우기의 규칙을 파악한다. 2-1) N이 1일 때 경우의 수는 2, N이 2일 때 경우의 수는 7이다. 2-2) N이 3이상일 때 N-1 크기에서 채우는 경우의 수는 2가지이다. 2-3) N-2 크기에서는 채우는 경우의 수는 3가지이다. 2-4) N-(3이상) 크기에서는 채우는 경우의 수는 2가지이다. 3) 재귀적으로 표현시 시간초과가 발생하기 때문에 모든 타일 채우는 경우의 수 배열의 2배를 더한 값을 저장하고 N번 째 경우의 수는 2배를 더한 값 + N-2의 경우의 수로..

[백준/JAVA] 2133번 타일 채우기

https://www.acmicpc.net/problem/2133 1. 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 2. 힌트 3. 문제 접근 1) 첫째 줄에 N의 크기를 입력받는다. 2) 경우의 수를 고려한 후 다이나믹 프로그래밍에 대한 점화식을 세운다. 2-1) 홀수인 경우 칸의 총 수가 홀수이기 때문에 2X1 혹은 1X2 크기의 타일로 채우지 못하기 때문에 0을 반환한다. 2-2) 짝수인 경우 크기가 2 작은 타일에서 채우는 경우의 수가 3가지이기 때문에 N-2를 매개변수로 하는 재귀함수에 3을 곱하는 경우를 가진다. 2-3) 짝수인 경우 중에 크기가 2보다 큰 짝수(4,6,8)만큼 작은 타일에서 채우는 경우의 수가 2가지이기 때문에 N-(2보다 큰 짝수)를..