less than 1 minute read

문제 풀이 방식

  • 전형적인 DP문제.
  • 이전의 2×n 타일링 문제와 거의 유사하다.
  • 점화식 : DP[i] = DP[i - 1] + 2 * DP[i - 2]

문제 풀이 (Java)

import java.util.Scanner;  

public class boj11727 {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        int n = scanner.nextInt();  
  
        int[] DP = new int[n + 2];  
  
        DP[0] = 0;  
        DP[1] = 1;  
        DP[2] = 3;  
  
        for (int i = 3; i <= n; i++) {  
            DP[i] = DP[i - 1] + 2 * DP[i - 2];  
            DP[i] %= 10007;  
        }  
  
        System.out.println(DP[n]);  
    }  
}

Leave a comment