[Java] 백준 풀기 11726 - 2xN 타일링

자바 백준 11726번

실버 3

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

11726번: 2×n 타일링

 

 

 

 

 

문제 보기

분류: 다이나믹 프로그래밍

 

 

 

 

 

문제 풀기

지속적으로 타일을 채우는 방법은 이전 타일을 채우는 방법의 연장선이기 때문에 Dynamic Programming을 이용하여 방법의 개수를 구한다.

n은 최대 1000까지 주어졌으므로 1001개의 array를 지정하여 모든 답을 저장하고 n에  대한 답만 출력한다.

 

n = 1 일때 방법의 수는 1

n = 2 일때 방법의 수는 2

이 두 초기화 값을 가지고 n = 3부터 다이나믹 프로그래밍을 이용하여 모든 방법의 수를 구한다. 문제에서 오버플로우를 막기 위해 소수인 10007을 나눈 나머지를 출력하도록 하였다. 따라서 dp를 구하는 과정에서 이 계산을 매번 시행해 주어야한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }
        
        System.out.print(dp[n]);
    }
    
}