[백준 9095번] 11726번 : 2xn 타일링 (자바)

백준알고리즘 11726번 : 2xn 타일링 (Solved.ac 난이도 Gold5)

 

요약 : 피보나치 수열의 규칙이 있는 DP 문제 

 

↑클릭시 문제 link로 이동합니다.😊

 

 

이 문제는 Dynamic Program 알고리즘 중 Top-down 방식으로 풀어보았다.

 

큰 단위를 작은 단위의 문제로 쪼개서 풀어야하는데,
내가 적절하게 잘 쪼개는지를 검증하기위해 최소 단위를 내가 직접 풀어보았다.

 

2xN 의 면적을 1x2의 타일과, 2x1의 타일로 채울 수 있는 집합의 개수를 구하는 문제이다.

 

따지고보면 경우의 수를 구하는 문제인데, 2x3의 타일부터 규칙이 생길것으로 판단되니(타일의 최대길이가 2이므로)

2x1과 2x2의 경우의 수를 구하고, 2x3의 경우의수가 하위 갯수의 집합의 합이 되는 DP로 구성되는지 검증해보아야겠다.

 

    2x1 : 1가지
    2x2 : 2가지
    2x3 : 3가지 (맨 왼쪽에 2x1 타일이 들어가는경우 -> 2가지) + (맨 왼쪽에 1x2 타일이 들어가는 경우 -> 1가지)

    2x4 : 5가지 (맨 왼쪽에 2x1 타일이 들어가는 경우 : (2x3의 가지수와 일치함 -> 3가지) +

                    (맨 왼쪽에 1x2 타일이 들어가는 경우 : (2x2의 가지수와 일치함 -> 2가지)

 

규칙이 보인다. 이제 구현하자.

 

풀이 과정

---

1. 작은 단위에서의 규칙을 찾는다.
2. 풀어야하는 문자를 받아온다음, 해당 길이만큼의 배열을 생성한다.(최대 1000까지 가능하여 나는 그냥 길이 1001의 배열을 생성했다.)
3. 재귀를 이용하여 dp(n) = dp(n-1) + dp(n-2) 라는 수식을 돌게하고, 중복하여 도는 것을 제거하기 위해 dp(x)의 값이 있다면 (이미 숫자가 부여되었다면) 바로 값을 return 시킨다.

 

몇 번 틀렸던 이유를 생각해보니, 변수 type을 long을 쓰더라도 마지막에 10007로 나누어주게되면 연산과정에서 overflow가 발생하는 것으로 보여, return시 10007로 나눈 나머지를 return하게 해주었더니 자료형을 int로 바꿔주어도 정답처리가 되었다. 연산과정에서 숫자가 커질 경우를 항상 반례로 염두에 두어야겠다.

 

 

 

▽ 정답 소스 보기

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

public class Main {// No11726 : 2×n 타일링
    static int[] method;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        method = new int[1001];
        method[1] = 1;
        method[2] = 2;
        System.out.println(dp(num));

    }

    public static int dp(int a) {
        if (method[a] != 0) {
            return method[a]%10007;
        } else {
            method[a] = dp(a - 1) + dp(a - 2);
            return method[a]%10007;
        }
    }
}