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

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

 

이 문제는 DP를 사용하여 풀 수 있다. 

 

코드는 다음과 같다. 자세한 설명이 필요하다면 아래 추천영상을 참고하길 바란다.

 

import java.util.Scanner;

public class Main {
	
	static int[] arr = new int[1001]; 
	static int[] N;
	static int result, a;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N1 = sc.nextInt();
		N = new int[N1+1];

		for(int i = 0; N1>i ; ++i) {
			N[i] = sc.nextInt();
		}
		for(int i = 0 ; N1 > i ; ++i) {
			System.out.println(dp(N[i]));
		}
	}
	
	public static int dp(int x) {
		
		if( x == 0 ) return 1; 
		if( x == 1 ) return 1;
		if( x == 2 ) return 5;
		if( x == 3 ) return 11;
		if(arr[x] != 0) return arr[x];

		result = dp(x-1) + 4*dp(x-2) ;
		
		for(int i=3; x>=i;++i) {
			if( i%2 == 0 ) {
				result += 3*dp(x-i);
			}
			if( i%2 != 0) {
				result += 2*dp(x-i);
			}
		}
		
		return arr[x] = result;
		
	}

} 

https://www.youtube.com/watch?v=YHZiWaL49HY&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=22

이 영상을 본 후 코드를 본다면 좀 더 이해를 빨리 할 수 있을 것이라 생각한다.