[백준 JAVA] 11726번 풀이 - 2xn 타일링

 

생각의 방향 

DP 알고리즘 개념을 처음 공부하고 스스로 푼 문제! 

바텀업(Bottom-up) 방법으로 푸는데 성공했다. 가장 까다로운 점은 '점화식 찾기' 였다. 

어떻게 풀어야할지 고민하다가, 일단 경우의 수를 직접 적어가며(머릿속으로 상상하고 그리며) 점화식을 도출해냈다. 

 

🔻 메모장에 적어가며 알아낸 점화식 

n=2
-> 2개 

n=3
[가로] [가로] [가로] -> 1
[세로] [세로] [가로] 
[가로] [세로] [세로] 
-> 3개 (1(=dp[1])+2(=dp[2]))

n=4
[][][][]
[][][][]
-> [가로][가로][가로][가로] (all 가로) -> 1
-> [세로][세로][세로][세로] (all 세로) -> 짝수일 때 가능 1
=> 2값 dp[2] 랑 동일. (거의 /2) 
-> [세로][세로][가로][가로]
-> [가로][세로][세로][가로]
-> [가로][가로][세로][세로]
=> 5개 (2(=dp[2])+3(=dp[3]))

 

난 이렇게 적어가면서 점화식을 도출해내고 문제를 맞췄지만, 직접 그려서 문제를 해결하는 분들의 포스팅을 보며, 그리면서 풀었으면 좀 더 빨리 풀었을텐데! ㅎㅎ 라는 생각을 했다. 

✨ dp[n-1] 과 dp[n-2] 의 합이 dp[n] 의 값

 

 

코드 

package quiz;

import java.util.Scanner;

/**
 * 2xn 타일링
 *
 * 2*n 크기의 직사각형을 1*2, 2*1 타일로 채우는 방법의 수를 구하시오.
 * 첫째줄에 n이 주어진다.
 * 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
 *
 * 2 - > 2
 * 9 -> 55
 *
 * if n=3,
 * n=1 일 때, 1개
 * n=2 일 때, 2개
 * n=3 일 때,
 *
 */
public class _11726_dp {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        // 위에서 올라가며 푸는 Bottom-Up 문제.
        // 1*2, 2*1 로 채운 결과를 dp 테이블에 저장한다.
        //2는 고정, n ...
        // 1) 1*2 로 모두 채우는 방법,
        int[] dp = new int[1001];

        //초기화!
        dp[2] = 2;
        dp[1] = 1; //1개 뿐.
        for(int i=3; i<=n; i++){
            //dp-1 과 dp-2 값을 합친것이 dp[i] 값!
            dp[i] = (dp[i-2] + dp[i-1]) % 10007;
            //System.out.println("dp[i] 는 " + "i값="+i + " , " + "결과는 = " + dp[i]);
        }

        System.out.println(dp[n]);

        sc.close();
    }
}