알고리즘

[이코테 with Java] 바닥 공사

크딩학생 2024. 1. 31. 14:48

문제

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥은 1 X 2 덮게, 2 X 1 덮개, 2 X 2 덮개를 이용해 채우고자 한다.

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2 x 3 크기의 바닥을 채우는 경우의 수는 5가지이다. 

 

입력 조건

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

출력 조건

  • 첫째 줄에 2 x N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

입력 예시

3

 

출력 예시

5

 

이 문제 또한 다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형이다. 다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어있는 경우가 많다. 이 문제에서도 796,796으로 나눈 나머지를 출력하라고 하는데, 이는 단지 결괏값이 굉장히 커질 수 있기 때문에 그런 것이다. 따라서 값을 계산할 때마다 특정한 수로 나눈 나머지만 취하도록 하면 된다.

 

왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있다.

1. 왼쪽부터 i - 1까지 길이가 덮개로 이미 채워져 있으면 2 x 1의 덮개를 채우는 하나의 경우밖에 존재하지 않는다.

 

 

왜냐하면 가로가 1인 블록이 하나밖에 존재하지 않기 때문이다. 

우리에게는 1 x 2(세로가 1, 가로가 2) , 2 x 2(세로가 2, 가로가 2)와 2 x 1 (세로가 2, 가로가 1) 인 경우만 있다. 

 

만약 i가 5라고 생각해보자. i가 5라면 i-1은 4이다. 4까지 채워져 있으면 나머지를 채우는 방법은 2 x 1 덮개를 채우는 하나의 경우밖에 없다.

 

2. 왼쪽부터 i - 2까지 길이가 덮개로 이미 채워져 있으면 1 x 2 덮개 2개를 넣는 경우, 혹은 2 x 2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다. 참고로 2 x 1 덮개 2개를 넣는 경우를 고려하지 않는 이유는 이미 1에서 고려되었기 때문이다. 

 

여기에서 왜 2 x 1 덮개 2개를 넣는 경우를 고려하지 않는지 설명을 해보겠다.

예를 들어, i가 4라고 가정을 해보자.

 

사진을 보면 3까지는 중복되는 것을 알 수 있다. 

그렇다면 왜 i-1까지 덮개로 채워져 있는 경우와 i-2까지 덮개로 채워져 있는 경우에 중복이 생길까?

왜냐하면 반드시 i 바로 이전의 i-1이 2x1이라면 같은 2x1이 두 개가 되기 때문이다.

 

i가 4가 아닌 5라고 해도 i-1의 블록이 2x1이라면 i가 2x1이기 때문에 2x1인 블록이 두 개가 된다.

즉, i-1이 2x1 블록인 경우 반드시 i-1~i까지 블록이 2x1이고, 2x1 블록이 두 개인 경우가 되기 때문에 

i-2까지 채워져 있고, 나머지를 2x1 블록으로 채우는 경우와 중복된다.

 

 

이 문제 역시 i번째 위치에 대한 최적의 해를 구할 때 왼쪽부터 (i - 3)번째 이하의 위치에 대한 최적의 해에 대해서는 고려할 필요가 없다. 왜냐하면 사용할 수 있는 덮개의 형태가 최대 2 x 2 크기의 직사각형 형태이기 때문이다. 다시 말해 바닥을 채울 수 있는 형태는 위에서 언급한 경우밖에 없다. 따라서 다음과 같이 점화식을 세울 수 있다. 

 

 

 

왼쪽부터 N - 2까지 길이가 덮개로 이미 채워져 있는 경우 덮개를 채우는 방법은 2가지 경우가 있다. 이 두 방법은 서로 다른 것으로, 결과적으로 a(i) = a(i-1) + a(i-2) + a(i-2)가 된다. 따라서 이를 간략하게 표현한 것이 위의 점화식이다. 

 

 

 

코드

import java.util.*;

public class Main {

    // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
    public static int[] d = new int[1001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 정수 N을 입력받기
        int n = sc.nextInt();


        // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
        d[1] = 1;
        d[2] = 3;
        for(int i = 3; i <= n; i++) {
            d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796;
        }

        // 계산된 결과 출력
        System.out.println(d[n]);
    }
}

 

이 코드는 n의 크기가 1일 때, 2일 때, 3일 때의 경우를 더해주고 있다. 

세로 길이는 고정되어 있고 가로 길이는 N 값으로 변하기 때문에, 가로를 작게 분해했다고 생각하면 된다. 

 

 

 

원래의 n의 길이를 1부터 n까지 바꾸는 것이 아니라, 각각의 묶음에 대해서 경우의 수를 출력한다고 생각하면 된다. 

 

i - 1이나 i - 2까지는 이미 채워져 있다고 가정하고, 나머지에 대한 코드를 짠다고 생각하면 쉽다.

위에 그려진 그림처럼 i-1까지 채워진 경우에는 2x1 블록 하나만 들어갈 수 있고, i-2까지 채워진 경우에는 1x2 블록 두 개나, 2x2 블록 하나가 들어가 총 세 가지 경우의 수가 있다. 

 

따라서 각각의 분해된 것들에 대해 덧셈을 수행하면, 최종적으로 가로의 길이가 n일 때의 경우의 수가 도출된다.