[BOJ] 11726 - 2xn 타일링 (Java)

알고리즘

• 다이나믹 프로그래밍

1. 문제

2. Idea

• dp[N]: (2xN 크기의 직사각형을 1x2,2x1 크기의 타일로 채우는 방법의 수) % 10,007
• N-1번째 경우에 |를 추가하는 경우 + N=2번째 경우에 =를 추가하는 경우로 나누어 생각
• 처음에 수학적으로 복잡하게 생각해서 조합 공식을 적용해보려 시도했었다..
  계속 그림 그려보고, dp문제인 만큼 앞 배열의 값을 어떻게 사용할지 고민해서 풀어내고 보니 어렵지 않았던 문제였다.

3. 풀이

3.1. 변수 선언 및 초기화

• int[] dp: 2xN 크기의 직사각형을 타일로 채우는 경우의 수를 저장한 배열
• int N: 직사각형 세로 길이
• dp[0], dp[1], dp[2] 값 추가

int[] dp=new int[1001];
int N=Integer.parseInt(br.readLine());
dp[0]=1;
dp[1]=1;
dp[2]=2;
dp[3]=3;

3.2. dp 배열 값 및 나머지 계산

• dp[N] = dp[N-1] + dp[N-2]
  • N-1번째 경우에 |를 추가하는 경우 + N=2번째 경우에 =를 추가하는 경우
    

for(int i=4; i<=N; i++){
	dp[i]=dp[i-2]+dp[i-1];
	if(dp[i]>=10007){dp[i]=dp[i]%10007;}
}

3.3. 결과 출력

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

4. 전체코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int[] dp=new int[1001];
        int N=Integer.parseInt(br.readLine());
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        for(int i=4; i<=N; i++){
            dp[i]=dp[i-2]+dp[i-1];
            if(dp[i]>=10007){dp[i]=dp[i]%10007;}
        }
        System.out.println(dp[N]);
    }
}