[이것이 취업을 위한 코딩테스트다] Ch08. 다이나믹 프로그래밍 - 바닥 공사 (Java)

문제

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

이 얇은 바닥을 1 * 2덮개, 2 * 1덮개, 2 * 2덮개 세 가지의 덮개를 이용하여 채우고자 함

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

예를 들어 2*3 크기의 바닥을 채우는 경우의 수는 5

* 출력 시 바닥을 채우는 방법의 수를 796796으로 나눈 나머지를 출력

(입력예시)

3

(출력예시)

5

풀이/후기

(다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라고 하는데,

단지 결과값이 굉장히 커질 수 있기 때문임)

다이나믹 프로그래밍의 기초 예제에서 필수적인 타일링 문제 유형임

 

코드

package ThisIsCT;

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

public class ch08_04 {
	// Ch.08 다이나믹 프로그래밍 Dynamic Programming DP
	// 바닥 공사
	
	static int[] d = new int[1000 + 1];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		
		/*
		 * 1) 왼쪽부터 i-1까지 덮개로 채워지면 2 * 1의 덮개로 채울 수 있음 -> 한가지
		 * 2) 왼쪽부터 i-2까지 덮개로 채워지면 2 * 2 또는 1 * 2의 덮개로 채울 수 있음 -> 두가지
		 * 
		 */
		
		d[1] = 1;
		d[2] = 3;
		for (int i=3; i<N+1; i++) {
			d[i] = (d[i - 1] + d[i - 2] * 2) % 796796;
		}
		System.out.println(d[N]);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/1c5739077cd1b0c1c4b5280414e8c036aa4b8902

참고