[백준 11726번] 자바/2×n 타일링

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

첫 번째 코드

냅다 그려봤다. 생각보다 규칙이 금방 보인다!

역시 틀렸다. 다시 생각해보니 내 점화식이 틀렸다... 두덩이(2X1)를 가로로 쌓을 때랑 정사각형(2X2)가 공존할 수 있다는 사실을 생각안했다...

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

public class BJ11727 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		
		System.out.println(solution(n, new Hashtable<>()) % 10007);
	}
	
	private static int solution(int n, Hashtable<Integer, Integer> memo) {
		// 종료 조건
		if(n == 1) {
			return 1;
		} else if(n == 2) {
			return 3;
		} else if(n == 3) {
			return 5;
		}
		
		// 순환
		int temp;
		
		if(memo.get(n - 1) == null) {
			temp = solution(n - 1, memo);
			temp = temp >= 10007 ? temp - 10007 : temp; 
			memo.put(n - 1, temp);
		}
		
		if(memo.get(n - 2) == null) {
			temp = solution(n - 2, memo);
			temp = temp >= 10007 ? temp - 10007 : temp; 
			memo.put(n - 2, temp);
		}
		
		if(memo.get(n - 3) == null) {
			temp = solution(n - 3, memo);
			temp = temp >= 10007 ? temp - 10007 : temp; 
			memo.put(n - 3, temp);
		}
		
		return memo.get(n - 1) + memo.get(n - 2) + memo.get(n - 3) - 1;
	}
}

---

두 번째 코드

시간이 많지 않아 다른 블로그 슬쩍 보고왔다.

https://girawhale.tistory.com/34

정리가 너무 깔끔해서 감탄하고 왔다... 우선 급하니 얼른 코드 다시 써보자구~

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

public class BJ11727 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		
		System.out.println(solution(n, new Hashtable<>()) % 10007);
	}
	
	private static int solution(int n, Hashtable<Integer, Integer> memo) {
		// 종료 조건
		if(n == 1) {
			return 1;
		} else if(n == 2) {
			return 3;
		} 
		
		// 순환
		int temp;
		
		if(memo.get(n - 1) == null) {
			temp = solution(n - 1, memo);
			temp = temp >= 10007 ? temp % 10007 : temp; 
			memo.put(n - 1, temp);
		}
		
		if(memo.get(n - 2) == null) {
			temp = solution(n - 2, memo);
			temp = temp >= 10007 ? temp % 10007 : temp; 
			memo.put(n - 2, temp);
		}
		
		return memo.get(n - 1) + 2 * memo.get(n - 2);
	}

}

아니 풀긴 풀었는데 참고한 블로그 코드랑 내 코드 길이랑 너무 차이나서 좀 놀랐다... https://girawhale.tistory.com/34

다이나믹 프로그래밍 구현하는데 두 종류가 있다고 수업시간에 들었던거 같은데(?) 참고하면 좋을거같아서 링크 남기고 끝낸다! ㅂㅇ!

https://semaph.tistory.com/16