[Java] 11726번: 2xn 타일링 Silver 3

문제 링크

1년 전쯤에 풀었던 종이 붙이기랑 매우 비슷했다.
풀이는 전에 네이버 블로그에 잘 정리해놨었다.
그림으로 보면 확실히 이해하기 쉽다.

그리고 블로그를 다시 보니 당시에 종이 붙이기에서 살짝 다르게 나오면 어떻게 구할 수 있을지 고민한 부분이 있는데, 그게 지금 이 문제랑 정확히 똑같았다 ㅋㅋ..

(아직까지 내가 알고 있는 걸로는..)
DP 문제를 푸는 방법은 N을 어떻게 만드는 지에 집중하는 것이다.
그리고 그걸 고민해서 점화식을 만들면 된다.

1. N-1 단계에서 N 단계로 오는 방법은 세로로 배치하는 방법(|) 1가지 밖에 없다.
2. N-2 단계에서 N 단계로 오는 방법은 가로로 배치하는 방법(=) 1가지 밖에 없다.

여튼 식을 적어보자면 이렇게 된다.

X[N] = X[N-1] + X[N-2]

처음에 1과 2는 기본 입력으로 배열에 대입해주고 나머지는 위 과정을 N까지 반복하면 된다!

정답

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

public class Main {
    private static int N;
    private static int[] dp;

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

        // N 입력 받기
        N = Integer.parseInt(br.readLine());

        // dp
        if (N == 1) {
            System.out.println(1);
        } else if (N == 2) {
            System.out.println(2);
        } else {
            dp = new int[N];
            dp[0] = 1;
            dp[1] = 2;
            for (int i = 2; i < N; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2]);
            }

            System.out.println(dp[N - 1]);
        }
    }
}