백준 11726 2xn 타일링 동적계획법 활용 2가지 풀이 ( Java )

11726번: 2×n 타일링

- Bottom-up ( 반복문 활용 ) 방식

 

import java.io.*;
 
public class Main{
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        // 1 <= n <= 1,000
        
        int[] memo = new int[1001];
 
        memo[1] = 1;
        // 기저 사례 1. 크기가 2 x 1 인 직사각형을 타일로 채우는 방법은 1가지 뿐이다        
        memo[2] = 2;
        // 기저 사례 2. 크기가 2 x 1 인 직사각형을 타일로 채우는 방법은 2가지 뿐이다
 
        for (int i = 3; i <= n; i++) {
            // 3부터 n까지는
            memo[i] = memo[i-1] + memo[i-2];
            // 기저 사례를 바탕으로 하나씩 쌓아나가고 
            memo[i] %= 10007;
            // 문제의 요구대로 10007로 나눈 나머지를 저장한다
        }
        
        bw.write(String.valueOf(memo[n]));
        // memo[n]을 출력한다
        bw.flush();
 
    }
 
}

 

- Top-down ( 재귀 함수 호출 ) 방식

 

import java.io.*;
 
public class Main{
 
    private static int[] memo;
 
    public static int tilling(int n) {
 
        if (n >= 0 && n <= 2) {
            memo[n] = n;
            // 기저 사례들 - 0,1,2 세팅
            return memo[n];
        }
 
        if (memo[n] > 0) {
            return memo[n];
        }
 
        memo[n] = tilling(n - 1) + tilling(n - 2);
        // 크기가 2 X N인 직사각형을 1 X 2, 2 X 1 타일로 채우는 방법의 수는
        // 마지막에 1 x 2 타일 하나가 올 때의 방법과 마지막에 2 X 1 타일 두개가 올 때의 방법의 합이다 
        memo[n] %= 10007;
 
        return memo[n];
 
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        // 1 <= n <= 1,000
 
        memo = new int[n + 1];
        // n 까지 저장해야하니 메모 배열 n+1 까지 생성
 
        int answer = tilling(n);
        // 크기가 2 X N인 직사각형을 1 X 2, 2 X 1 타일로 채우는 방법의 수
 
        bw.write(String.valueOf(answer));
        bw.flush();
 
    }
 
}

 

동적 계획법 문제들은 결국 점화식을 구하는 게 중요한 것 같다.

헷갈릴 때는 동적 계획법의 정의에 대해 다시 한번 상기해보고 문제에 접근하자