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

이 문제는 DP를 사용해서 풀 수 있다. 

 

N의 수가 크기때문에 1차원 dp를 사용한다면 시간초과가 된다.

 

그러므로 2차원 배열을 이용하여 dp를 해주면 된다.

 

또한 값을 저장하는 배열의 값이 21억이 넘는 경우가 발생하여 int 형으로 선언한다면 런타임에러가 뜨는 것만 조심해야한다. 

 

이해가 잘 되지 않으면 아래 추천 영상을 보면서 이해하길 바란다.

import java.util.Scanner;

public class Main {

	private static final int MOD = 1000000007;
	static long[][] arr;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		arr = new long[1000001][2];

		System.out.print(dp(N));
	}

	public static long dp(int x) {

		arr[0][0] = 0;
		arr[1][0] = 2;
		arr[2][0] = 7;
		arr[2][1] = 1;
		
		for(int i = 3; x>= i; i++) {
			arr[i][1] = (arr[i-1][1] + arr[i-3][0]) % MOD;
			arr[i][0] = (2*arr[i-1][0]+3*arr[i-2][0] + 2*arr[i][1]) % MOD;
		}
		return arr[x][0];
	} 
}
 

 

https://www.youtube.com/watch?v=kYoKLm8BZtI&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=23

(6분 20초 정도부터 문제 14852 에 관한 내용임.)