[JAVA] 백준 11727 2×n 타일링 2

U_Uracil·2022년 9월 18일
0

알고리즘 JAVA

목록 보기
2/19

[백준 11727]https://www.acmicpc.net/problem/11727


문제 조건

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수


문제 입력

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


문제 풀기 전 설계

이전의 결과가 뒤의 결과를 도출하는데 도움되는 문제니까 Dynamic Programming(DP : 동적계획법)으로 풀어야 할 것 같다.


문제 코드

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


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 3;

        for (int i = 3; i <= n; i++) {	// 점화식
            dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
        }

        System.out.println(dp[n]);
    }

}

문제 풀이


이 문제는 이렇게 i번째 경우의 수가 (i - 1)번째와 (i - 2)번째 경우의 수에 의해 결정된다.
점화식은 dp[i] = dp[i - 1] + 2 * dp[i - 2]로 세울 수 있다.


Review

dp문제는 점화식을 세우는 게 가장 중요한데, 여러 문제를 풀어보면서 문제에서 주어진 패턴을 파악하고 점화식으로 나타내는 연습을 많이 해야겠다.

profile
기억은 유한, 기록은 무한

0개의 댓글