[정올][다이나믹] 1411 두 줄로 타일 깔기

두줄로 타일깔기는 라인 길이에 따라 타일을 배열하는 방법을 생각해서 처리하면된다. 

구현할 때 재귀를 이용하여 처리하면 stack overflow 가 발생한다. 

f(n) 을 구하는 방법은 

f(n-1) 의 타일 개수에 1 x 2 타일을 하나 추가하는 방법과

f(n-2)의 타일 개수에 2 x 2 타일을 추가하는 방법 

두개를 더하면 된다. 

	import java.util.Scanner;
	/**
	* 정올, 1411, 다이나믹
	* 두 줄로 타일 깔기
	*
	* @author whitebeard-k
	*
	*/
	public class Problem1411 {
	public static int[] memo = new int[1000001];
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	sc.close();
	memo[1] = 1;
	memo[2] = 3;
	for(int i = 3; i <= n; i++) {
	memo[i] = ((memo[i-1]) + (2*memo[i-2]))%20100529;
	}
	System.out.println(memo[n]);
	}
	}

view raw Problem1411.java hosted with ❤ by GitHub

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=687&sca=3050

http://huiyu.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%ED%83%80%EC%9D%BC-%EC%B1%84%EC%9A%B0%EA%B8%B0-%EB%AC%B8%EC%A0%9C