[BOJ][Java] 백준 2718번: 타일 채우기

1일 1PS 25일차!

📚 문제

---

골드 1

• DP 문제인데 쉽게 생각했지만 예외가 발생한다.
• Dp[i] = Dp[i - 1] + Dp[i - 2] * 4 까지는 쉽게 생각할 수 있다.
• 여기서 문제가 발생하는 부분은 가로로 배치되는 타일이 계속해서 한 칸씩 겹치는 부분이다.
• 쉽게 생각해보자면 n = 3 일 때 아래와 같은 모양 때문에 문제가 발생한다.

• 따라서 Dp[6] 을 구하는 과정은

  • Dp[5] + 4 * Dp[4] +
  • (N=3 일 때 2가지 이므로) 2 _ Dp[3] + (N=4 일 때 3가지 이므로) 3 _ Dp[2] + 2 _ Dp[1] + 3 _ Dp[3]

• 이때 n = i + j 로 i, j 로 나눌 때

  • i 가 홀수 => 2 * dp[j]
  • i 가 짝수 => 3 * dp[j]

💡 포인트

---

1. 동적 리스트를 만들기 위해 ArrayList 를 선언한다. (int [10001] 정도로 선언해도 충분할 것 같다.)
2. Dp 에 있는 n 인지 확인하고 없으면 위처럼 계산한다.

💻 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

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

        int T = Integer.parseInt(br.readLine());
        int N;
        List<Integer> dp = new ArrayList<>();
        dp.add(1);
        dp.add(1);
        dp.add(5);

        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine());

            if (N < dp.size()) {
                System.out.println(dp.get(N));
            } else {
                for (int j = dp.size(); j <= N; j++) {
                    int result = (Integer) dp.get(j - 1) + (Integer) dp.get(j - 2) * 4;

                    for (int k = 3; j >= k ; k++) {
                        if (k % 2 == 0){
                            result += 3 * (Integer) dp.get(j - k);
                        } else {
                            result += 2 * (Integer) dp.get(j - k);
                        }
                    }
                    dp.add(result);
                }
                System.out.println(dp.get(N));
            }

        }
    }
}