[백준] 11726 2xn 타일링 (자바) : DP [실버 3]

이번 포스팅에서는 DP 알고리즘 백준 11726 2xn 타일링 문제를 풀어보도록 하겠습니다. 

상세한 설명 포함 !! 

✔️ 문제 설명 (펼치기)

 

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

✔️ 문제 풀이

[의식의 흐름]

 

1. 처음에는 n이라는 숫자를 1의 배수의 합과 2의 배수의 합으로 나타내야 한다고 생각했다. 

2. a+2b = n 이라는 방정식을 세웠다 .

3. for 문을 활용해서 a와 b를 어떻게든 구할 수 있겠다. 

4. n이 5일 때 2x1 타일이 1개이고 1x2 타일이 2개 일 때, 각 타일을 어디다가 배치할지에 대한 고민이 생긴다. 

위의 그림처럼 타일을 배치하는거에 따라서 배치를 할 수 있을 수도 있고, 없을 수도 있다. 

가령 아래의 그림처럼 2x1 타일을 배치하면, 1x2 타일 2개를 배치할 수 없다. 

 

그럼 어떻게 배치의 경우의 수를 찾을 수 있을까? 하다가

1,2,3 더하기 문제에서 사용했던 알고리즘이 떠올랐다. 

 

우선 세로의 길이가 2로 정해져있으므로 가로의 길이를 1과 2를 이용해서 만들면된다. 

dp[i] 를 경우의 수라고 생각했을 때,

dp[1] 은 2x1 직사각형 이므로, 가로가 1이다. 그래서 가로가 1인 타일만 들어갈 수 있으므로 경우의 수는 1이다. 

dp[2] 는 2x2 직사각형 이므로, 가로가 2이다. 가로가 2인 타일을 2개 배치하든, 가로가 1인 타일을 2개 배치하든 경우의 수가 2이다. 

가로	방법의 수	케이스
1	1	1
2	2	1+1, 2
3	3	[1+2], [1+1+1, 2+1]
4	5	[1+1+2, 2+2] , [1+2+1, 1+1+1+1, 2+1+1]
5	8	[1+2+2, 1+1+1+2, 2+1+2], [1+1+2+1, 2+2+1, 1+2+1+1 , 1+1+1+1+1 , 2+1+1+1]

 

3의 경우,

1에서 2을 더하면 3를 만들 수 있다. 따라서 1의 케이스에서 2을 더한다. 

2에서 1를 더하면 3를 만들 수 있다. 따라서 2의 각각의 케이스에서 1를 더한다. 

 

4의 경우에도,

2에서 2을 더하면 4를 만들 수 있다. 따라서 2의 각각의 케이스에서 2을 더한다.

3에서 1를 더하면 4를 만들 수 있다. 따라서 3의 각각의 케이스에서 1를 더한다. 

 

점화식을 구해보면, dp[i] = dp[i-2] + dp[i-1] 이다. 

 

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n+1];

        dp[1] = 1;
        if(n>= 2) dp[2] = 2;
        for(int i = 3; i<= n; i++){
            dp[i] = (dp[i-2] + dp[i-1])% 10007;
        }
        System.out.println(dp[n]);
    }
}

 

 

➕) 마주한 오류들

1. 오버플로우

	for(int i = 3; i<= n; i++){
            dp[i] = dp[i-2] + dp[i-1];
        }
        System.out.println(dp[n]%10007);

위의 경우 처럼 마지막 답을 출력할 때 10007의 나머지 연산을 하는경우이다. 

n은 1000이하의 정수인데, ...34,55,89... 이렇게 연산을 하다보면 수가 기하급수적으로 늘어나 int형이 담기지 못 한다. 

 

그래서 경우의 수를 구할 때 10007 나머지 연산을 구하는 방식으로 개선하였다. 

 

 

2. 런타임 에러(Array Index Out Of Bounds)

        int[] dp = new int[n+1];

        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i<= n; i++){
            dp[i] = (dp[i-2] + dp[i-1]) % 10007;
        }

 

위의 경우처럼 n이 1일 때, dp의 크기는 int[2] 가 된다. 즉, n이 1 인 경우 dp[2]에 접근하려고 할 때 오류가 발생하는 것이다. 

해결책은 두가지가 있다. 

•  n의 크기 조건문 넣기 → n의 크기가 2이상 일 때만 dp[2]에 접근

 	int[] dp = new int[n+1];
    	dp[1] = 1;
        if(n>= 2) dp[2] = 2;
        for(int i = 3; i<= n; i++){
            dp[i] = (dp[i-2] + dp[i-1])% 10007;
        }

• dp의 크기를 처음부터 n의 최댓값인 1001로 지정

 int[] dp = new int[1001];