[이.코.테] Chapter 08 동적 프로그래밍 - 바닥공사 (java)

바닥공사 문제 (교재 223p)

난이도 ●◐○ | 풀이 시간 20분 | 시간 제한 1초 | 메모리 제한 128MB

 

문제가로의 길이가 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

---

문제 풀이 방법

- i번째의 바닥을 채우는 방법

1. (i-1)까지 길이가 이미 채워져 있으면, 2 X 1공간만 남아 2 X 1로 채우는 경우는 하나뿐이다. : $a_{i-1}$가지
2. (i-2)까지 길이가 이미 채워져 있으면, 2 X 2공간이 남으며,
   1 X 2 2개를 넣는 경우와 2 X 2 하나를 넣는 2경우가 존재한다. :  $a_{i-2}+a_{i-2}$가지

 

* N - 2 미만의 길이에 대해서는 고려할 필요가 없다. 왜냐하면 사용할 수 있는 덮개의 형태가 최대 2 X 2의 직사각형 형태이기 때문이다.

점화식으로 표현해보면 아래와 같다.

$a_{i}=a_{i-1}+a_{i-2}+a_{i-2}$

 

소스 코드

import java.io.*;

public class Q3_Tile {
    public static int solution(int n){
        int[] a = new int[n+1];

        a[0] = 1;
        a[1] = 1;

        for (int i = 2; i < a.length; i++) {
            a[i] = (a[i - 1] + a[i - 2] * 2) % 796796;
        }

        return a[n];
    }

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

        int n = Integer.parseInt(br.readLine()); // 가로의 길이
        bw.write(solution(n)+"\n");
        br.close();
        bw.close();
    }
}

 

---

백준 동일하지만 796796만 다른 문제

11727번: 2×n 타일링 2