JAVA - 백준 알고리즘 - 2133 타일 채우기

https://www.acmicpc.net/problem/2133

 

이 문제는 DP (동적 계획법) 알고리즘을 사용하면 풀 수 있는 문제이다.

 

자세한 설명은 주석을 참고하면 된다.

 

dp를 풀때는 아무것도 하지 않는 경우도 경우의 수 1로 본다는 것을 알아두어야겠다.

import java.util.Scanner;

public class Main {
	
	static int[] arr = new int[31];  // dp 값 저장을 위한 배열
	static int result;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();  // 입력
		
		System.out.print(dp(N));  // 출력
		
	}
	
	public static int dp(int x) {
		
		if( x == 0 ) return 1;   // 3x0 에 타일을 채울 수 있는 경우의 수는 1개 (아무것도 놓지 않는 경우) / 이 경우를 빼면 런터임 에러가 발생함.
		if( x == 1 ) return 0;	 // 3x1 에 타일을 채울 수 있는 경우는 0개
		if( x == 2 ) return 3;   // 3x2 에 타일을 채울 수 있는 경우는 3개
		if(arr[x] != 0) return arr[x];

		result = 3*dp(x-2);
		
		for(int i = 3; x>= i ; ++i) {    // x-4 , x-6 , x-8 , ~~~ 0 에서 각각 2개의 경우의 수가 추가로 발생된다. 위에서 x가 0일때의 return 설정을 하지 않으면 여기서 에러발생.
				result += 2*dp(x-i);
			}
		}
		return arr[x] = result;
}