DP - 11727. 2×n 타일링 2

문제

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

잠깐만

11726. 2xn 타일링 문제 풀어보셨나요? 유사한 문제니, 같은 방법으로 풀어보세요

skillist.tistory.com/226

DP - 11726. 2×n 타일링

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int target = Integer.parseInt(st.nextToken()); 
		if (target == 1) {
			System.out.print(1);
			return;
		}
		
		long f1 = 1;
		long f2 = 3;
		
		for (int n = 3; n <= target; n++) {
			long fn = ((f1*2) + f2) % 10007;
			f1 = f2;
			f2 = fn;
		}
		
		System.out.print(f2);
	}
}

피보나치 문제의 답을 가져다 썼습니다.

 

설명

11726 문제 풀어보셨죠?

차이점은 2x2 블록이 추가됐다는것 뿐이에요

뭐 아무것도 아니네요?

 

2x1과 2x2 직사각형을 볼게요

이런 모양이 나오겠죠??

 

2x3 타일을 볼게요

2x3타일 = (2x2타일에 2x1타일 하나 추가) + (2x1타일에 1x2타일 두개 추가한 모양) + (2x1타일에 2x2타일 두개 추가한 모양)

 

2x4 타일을 볼게요

2x4타일 = (2x3타일에 2x1타일 하나 추가) + (2x2타일에 1x2타일 두개 추가한 모양) + (2x2타일에 2x2타일 두개 추가한 모양)

 

2x5 타일은 알겠죠?

2x5타일 = ? (어떤 값이 들어가야할지 맞춰보세요)

회고

마음 가다듬고 천천히 가자구요~