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

11727번: 2×n 타일링 2

- 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] = 3;
        // 기저 사례 2. 크기가 2 x 1 인 직사각형을 타일로 채우는 방법이 3가지다. 
        // 1 x 2 두개 놓거나 2 x 1 두개 놓거나 2 x 2 하나 놓거나
        // 즉 마지막에 좌우로 2칸짜리 블록을 놓을 수 있는 방법이 두가지다
 
        for (int i = 3; i <= n; i++) {
            memo[i] = memo[i-1] + (2 * memo[i-2]);
            // 위의 기저 사례를 바탕으로 하나씩 쌓아나가고 
            memo[i] %= 10007;
            // 나머지 연산 + 저장
        }
        
        
        bw.write(String.valueOf(memo[n]));
        bw.flush();
 
    }
 
}

 

- Top-Down ( 재귀 호출 활용 ) 방식 -

 

import java.io.*;
 
public class Main {
 
    private static int[] memo;
 
    public static int tilling(int n) {
 
        if (n == 1) {
            memo[n] = 1;
            return memo[n];
        }
        
        if (n == 2) {
            memo[n] = 3;
            return memo[n];
        }
 
        // 기저 사례 세팅
        
        if (memo[n] > 0) {
            return memo[n];
        }
        
        // 메모된 값이 있으면 메모된 값 출력
 
        memo[n] = tilling(n - 1) + (2 * tilling(n - 2));
        // tilling(int n) = tilling(n - 1) + (2 * tilling(n - 2)) 란 점화식을 활용해 값 저장후
        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];
 
        int answer = tilling(n);
        // 크기가 2 X N인 직사각형을 1 X 2, 2 X 1 타일로 채우는 방법의 수
 
        bw.write(String.valueOf(answer));
        // 출력
        bw.flush();
 
    }
 
}

 

쓸 수 있는 블록이 하나 추가된 것 외에는 1탄과 크게 다르지 않다