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

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

14852번: 타일 채우기 3

 

대표적인 2차원 dp문제다.

나동빈님 알고리즘 강의(https://www.youtube.com/watch?v=kYoKLm8BZtI)를 보면서 이해했는데

2차원 dp를 사용할 때부터 설명이 많이 생략되어 이해하기 힘들었고,

구글링 해도 자세한 설명이 나오지 않았다.

나중에 까먹었을 때 다시 이해하기 위한 설명을 적어본다. (내 방식대로 적었기 때문에 참고하긴 어려울듯 싶다)

 

점화식 세우는 과정과 1차원 dp를 사용하는 코드는 따로 설명 x 유튜브 링크 참고.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static long[] d = new long[1000001];
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		System.out.println(dp(n));
	}
	static long dp(int n) {
		if(n == 0) return 1;
		if(n == 1) return 2;
		if(n == 2) return 7;
		if(d[n] != 0) return d[n];
		d[n] += (2 * dp(n-1) + 3 * dp(n-2)) % 1000000007;
		for(int i=3;n-i>=0;i++) {
			d[n] += (2 * dp(n-i)) % 1000000007;
		}
		return d[n] % 1000000007;
	}

}

위 코드는 시간 초과가 뜨는 1차원 dp 코드

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static long[][] d = new long[1000001][2];
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		d[0][0] = 1;
		d[1][0] = 2;
		d[2][0] = 7;
		d[2][1] = 0;
		System.out.println(dp(n));
	}
	static long dp(int n) {
		for(int i=3;i<=n;i++) {
			d[i][1] = (d[i-3][0] + d[i-1][1]) % 1000000007;
			d[i][0] = (2 * d[i-1][0] + 3 * d[i-2][0] + 2 * d[i][1]) % 1000000007;
		}
		return d[n][0];
	}

}

위 코드는 2차원 dp를 이용하는 코드

 

 

이해 안됐던 부분

1) 왜 arr[n][1]을 구하는 식이 arr[n-3][0] + arr[i-1][1]인지

2) 왜 arr[0][0] = 0이고, arr[2][1]이 1인지 (코드에는 반대지만 유튜브에는 이렇게 되어있음)

 

 

 

 

먼저 1)부터 해결해보자.

 

2차원 배열의 인덱스 1값, 즉 [n][1] 값을 구하는 식을 이해하지 못했으므로

해당하는 부분의 규칙을 찾아야 한다.

 

먼저, 이해하기 위해 시간 초과 에러가 나는 코드 기준으로 값을 직접 대입해봤다

n=5인 경우, d[5] = 2*d[4] + 3*d[3] + 2*d[2] + 2*d[1] + 2*d[0]

n=4인 경우, d[4] = 2*d[3] + 3*d[2] + 2*d[1] + 2*d[0]

 

두 식의 앞에 값 두개는 [n-1][0], [n-2][0] 을 통해 구할 수 있다.

남은건 n=5일 때 d[2] d[1] d[0]

            n=4일 때 d[1] d[0] 

이고, 이 값들이 인덱스 1의값 d[5][1], d[4][1]이 될것이다.

 

인덱스 1값을 구할때 점화식을 세우려면 이전값에서 무조건 가져와야하므로

n=5일때의 남은 d[1] d[0]은 당연히 n=4에서 가져와야할, d[4][1]이 될 것이다.

그럼 d[2] d[1] d[0] --> d[2] d[4][1]이 된다.

(1차원 배열으로 적은 경우는 시간초과 에러가 나는 코드 기준의 배열이다)

 

이제 남은건 d[2]이다.

d[2]의 값은 2차원 dp로 나타내면 d[2][0]이다. (2차원 dp일 경우 인덱스0값이 실제 구할값이므로)

 

즉, n=5일때의

d[5] = 2*d[4] + 3*d[3] + 2*d[2] + 2*d[1] + 2*d[0]

를 2차원 dp의 식으로 바꾸면

d[5][0] = 2*d[4][0] + 3*d[3][0] + 2*(d[2][0] + d[4][1]) 과 같다.

d[2][0] + d[4][1] 이 d[5][1]과 같으므로

다시 써보면 d[5][0] = 2*d[4][0] + 3*d[3][0] + 2*d[5][1]이다.

 

이를 또 다시 점화식으로 바꾸면

d[n][1] = d[n-3][0] + d[n-1][i]

d[n][0] = 2*d[n-1][0] + 3*d[n-2][0] + 2*d[n][1] 이다.

즉 코드와 같은 점화식이 도출된다.

 

 

 

그리고 2)를 해결하기 위해

n=3을 대입해본다.

시간초과 에러가 나는 코드 기준으로 하면

d[3] = 2*d[2] + 3*d[1] + 2*d[0] 

       = 2*7 + 3*2 + 2*1

       = 22

 

2차원 dp의 코드 기준으로 하면

d[3][0] = 2*d[2][0] + 3*d[1][0] + 2*d[3][1] 이다.

 

위 식 두개를 비교해보면 d[3][1] = 1 이 되어야 한다.

즉, d[3][1] = d[0][0] + d[2][1] = 1 이다.

 

애초에 시간초과 에러가 나는 코드에서도

d[0] = 1으로 두었기 때문에 (타일을 하나도 사용하지 않는 경우 1)

d[0][0] = 1이고, d[2][1]은 0으로 설정했다.

d[2][1]은 계산으로 대입되는 값이 아닌 그 다음값 계산을 위해 설정해두는 값이므로

배열의 초기값 0 으로 두는게 맞다.

물론 값을 바꾸어도 결과는 똑같지만 이렇게 해야 논리가 맞는다.

 

 

 

 

이렇게 해서.. 의문 두개 모두 해결 완료!

 

 

 

무엇이든 하나씩 차근차근 추론해나가면 이해할 수 있는 것 같다.

너무 풀어서 쓴 것 같지만

미래의 내가 잘 알아볼 수 있길..