[백준] 11727번 2×n 타일링 2 JAVA (자바) 풀이

문제 11727번 (DP)

 :  2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수

 

    아래 그림은 2×17 직사각형을 채운 한가지 예

 

 

 

[입력]

 :  첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

[출력]

 :  첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

1. 경우의 수는 2가지 

• 1x2  /  2x1  /  2x2
• 3가지 방식으로 표현할 수 있지만 경우의 수는 2가지로 나눈다
  • 2X1 타일의 경우 2x1짜리 타일만 들어갈 수 있다 즉 1x2는 모양에 맞지 않는다
    
  • 하지만 2X2 타일부터는 1x2 타일도 사용이 가능하다
    
  • 고로 2x1 타일은 개별적으로 dp를 생성하고 2x2 타일이랑 1x2타일은 같은 경우의 수로 생각하고 2배만 곱해주면 된다

 

2. dp

• 2x1 타일 택할 경우 : dp[i-1]
• 2x2 와 1x2 타일 택할 경우 : 2*dp[i-2]

 

 [코드]

import java.io.*;
import java.util.*;
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[1001];
        
        dp[1]=1;
        dp[2]=3;
        
        for(int i = 3; i<=N ; i++){
            dp[i] = (dp[i-1] + 2*dp[i-2])%10007;
        }
            
        System.out.println(dp[N]);
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int dp[] = new int[1001];
        
 :  dp[1]=1; 크기가 2X1면 2x1 타일 1개 필요
    dp[2]=3; 크기가 2X2면 2x1 타일 2개 / 1x2 타일 2개 / 2x2타일 1개 필요
        
 :  for(int i = 3; i<=N ; i++){
            dp[i] = (dp[i-1] + 2*dp[i-2])%10007;  2x1타일을 택할 경우와 2x2 혹은 1x2 타일을 택할 경우
    }
            
 :  System.out.println(dp[N]);  결과 출력
 
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

https://www.acmicpc.net/problem/11727

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *