[다이나믹 프로그래밍] 문제 이름 : 바닥 공사

문제 설명

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

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

 

입력조건- 첫째 줄에 N이 주어진다. (1 <= N <= 1000)

 

출력조건- 첫째 줄에 2xN 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다. (단지 결과값이 굉장히 커질 수 있기 때문에 나누는 것임)

 

사용 개념

다이나믹 프로그래밍

 

문제 해결 아이디어 

*과정

1. 도식화, 그림으로 그려 생각하기

2. 점화식 도출

 

*설명

왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면, 

• 왼쪽부터 i-1까지 길이가 덮개로 이미 채워져 있는 경우 → 2x1 덮개 1개 (1가지 경우)
• 왼쪽부터 i-2까지 길이가 덮개로 이미 채워져 있는 경우 → 1x2 덮개 2개 or 2x2 덮개 1개 (2가지 경우)

사용할 수 있는 덮개의 형태가 최대 2x2이기 때문에 N-2 미만의 길이에 대해서는 고려하지 X (만약 덮개의 길이가 더 다양하다면, 추가로 경우를 구하면 됨)

 

점화식으로 표현하면,

aᵢ : 주어진 바닥의 가로 길이가 i일 때 바닥을 채우는 모든 경우의 수 

코드 

import java.util.*;

public class Main {
	
	// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
	public static int[] result = new int[1001]; // N의 최대값: 1000 
	
	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);
		
		// N 입력받기 
		int N = kbd.nextInt();
		
		result[1] = 1;	// N = 1일 때 바닥을 채우는 모든 경우의 수
		result[2] = 3;	// N = 2일 때 바닥을 채우는 모든 경우의 수 
		for(int i = 3; i <= N; i++) {
			result[i] = (result[i-1] + result[i-2]*2) % 796796;
		}
		
		System.out.println(result[N]);	// 최종으로 구하는 값(N일 때 바닥을 채우는 모든 경우의 수)
		
	}

}