[백준] 11726번: 2xn 타일링(DP)

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

11726번: 2×n 타일링

코드

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

public class Main{

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bf.readLine());
		int[] dp = new int[1001];
		dp[1] = 1;
		dp[2] = 2;
		for(int i=3; i<=1000; i++) {
			dp[i] = (dp[i-2] + dp[i-1]) % 10007;
		}
        
		System.out.println(dp[n]);
		bf.close();
	}

}

풀이

DP로 구현했다.

위 그림을 보면 맨 오른쪽에 놓을 수 있는 경우의 수는

2x1 타일을 세로로 하나만 놓는 경우 -> d[n-1]

2x2 타일을 가로로 두개 놓는 경우 -> d[n-2]로,

d[n] = d[n-1] + d[n-2] 의 점화식이 나온다.(피보나치 수열)

 

https://antaehyeon.github.io/devlog/2018/05/08/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-2xn%ED%83%80%EC%9D%BC%EB%A7%81-(11726)/

 

또한 주의할점은, n이 1000까지 있으므로 점화식의 결과에서 10007의 나머지를 저장해주지 않으면 int 배열의 범위를 벗어나게 된다. 따라서 더할때, 10007을 나눈 나머지를 저장하면 오버플로우가 발생하지 않는다.