[이코테] DP - 바닥 공사 - JAVA

💡 문제

문제가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.

태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.

이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최솟값을 출력한다.
• 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

💬 입출력 예시

입력

3

출력

5

📌 풀이(소스코드)

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

// 바닥 공사
public class DP_03 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int d[] = new int[1001];

        // DP 테이블 초기화
        d[1] = 1;
        d[2] = 3;

        // 점화식에 맞는 반복문 실행
        for (int i = 3; i < n + 1; i++) {
            d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796;
        }
        System.out.println(d[n]);
    }
}

📄 해설

• 점화식 유도 못해서 해설 보고 풀이하였음
• 나중에 다시 풀어보면서 점화식 직접 유도해봐야함