[java][boj][s3] 11726. 2×n 타일링

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

11726번: 2×n 타일링

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

풀이

/*
 * 입력
 * 1. n
 * 출력
 * 1. 2xn 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지
 * 조건
 * 1. 1x2, 2x1로만 채워야 함
 *
 * >> 1 2 3 5 8 13...
 */

역시 모르는 문제가 나왔을 때는 무조건 써보는게 직빵이다 

이렇게 1 2 3 5 8 13 순서로 DP[i] = DP[i-1] + DP[i-2] 공식이 나오게 된다 10007로 나눈 나머지를 각각 구해야 하니 for문 안에서 구해 주면 된다

코드

package A형대비;

import java.io.*;
import java.util.*;

public class s3_11726_2xn타일링 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] DP = new int[1000];
		
		DP[0] = 1;
		DP[1] = 2;
		
		for(int i = 2; i<N; i++) {
			DP[i] = (DP[i-1] + DP[i-2])%10007;
		}
		
		System.out.println(DP[N-1]);

	}

}

결과

 

#자바 #java #boj #백준 #알고리즘