[백준 - 1904번] 01타일 - 자바(JAVA) 정리 및 해설 &1일 1DP- 7일차

1904번: 01타일

어떤식으로 풀었는가?

01타일은 동적계획법으로 푸는 문제이다. 01타일의 특이한 점은 n에따른 증가폭이 어디서 본것 같은 모양새로 증가합니다.

N = 1일때 1개 (1)

N =2 일때 2개 (00, 11)

N = 3일떼 3개 (100, 001, 111) 

N= 4일떼 5개 (0011, 0000, 1001, 1100, 1111 )
.....

즉, 1,2,3,5,8.... 이런식으로 느는것이 마치 피보나치 처럼 증가하는 것처럼 보입니다.

이때의 계산을 할때는 Bottom-Up 방식으로 피보나치 함수처럼 계산하면서 올라오면 됩니다.

/** 2020. 2. 24. 오후 11:18:10
 * @author ventulus95
 */
package codeBaekJoon;

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

public class No1904_01Tile {
	
	static int cache[] = new int [1100000];

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		cache[1] = 1;
		cache[2] = 2;
		for(int i=3; i<1100000; i++){
			cache[i] = (cache[i-1]+cache[i-2])%15746; 
		}
		System.out.println(cache[n]);
	}

}