[백준-11726번 자바/java] 2×n 타일링 _디버깅의 눈물

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

11726번: 2×n 타일링

 

 

 

 

2×n 타일링 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

121034

46027

33906

35.842%

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

 

 

 

---

 

 

체크 포인트

1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법) 이용

-큰 문제를 여러 가지 작은 문제로 나누어 해결해보는 DP를 이용했다.

-그 중에서 큰 문제로부터 작은 문제로 뻗어나가는 top-down(탑다운)방식을 이용해 재귀함수로 해결했다.

 

-2xn 크기 직사각형을 채우는 방법의 수를 확인해보면,

 

 

n	2xn 크기 직사각형을 채우는 방법의 수
1	1
2	2
3	3
4	5
5	8
6	13
...	...

 

2x3 크기 직사각형을 채우는 방법의 수 = 2x2 크기 직사각형을 채우는 방법의 수 + 2x1 크기 직사각형을 채우는 방법의 수

 

2x4 크기 직사각형을 채우는 방법의 수 = 2x3 크기 직사각형을 채우는 방법의 수 + 2x2 크기 직사각형을 채우는 방법의 수

 

2x5 크기 직사각형을 채우는 방법의 수 = 2x4 크기 직사각형을 채우는 방법의 수 + 2x3크기 직사각형을 채우는 방법의 수

 

...

 

2xn크기 직사각형을 채우는 방법의 수

=

2x(n-1)크기 직사각형을 채우는 방법의 수 + 2x(n-2)크기 직사각형을 채우는 방법의 수

 

 

임을 추론할 수 있다.

 

 

 

2.  10,007로 미리 나누기

-모든 연산이 끝난 후에 10,007로 나누려면 오답이 된다. 왜냐하면 직사각형을 채우는 방법의 수가 최종 연산 전에 int의 크기를 넘어설 수 있기 때문이다.

 

dp[N] = (solution(N-1) + solution(N-2))%10007;

 

-따라서 위와 같이 하나의 연산이 진행될 때마다 나누기 연산을 적용해야 한다.

 

 

 

 

 

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	
	// 메모이제이션을 활용할 dp 배열
	static Integer[] dp;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	// (1<= N <= 1000) 
    	int N = Integer.parseInt(st.nextToken());
    	
    	// dp 배열 초기화
    	dp = new Integer[N+1];
    	// 0번째, 1번째 값 초기화
    	dp[0]=0;
    	dp[1]=1;
    	
    	// N=1이 아닐 경우에만 dp[2] 초기화
    	// 그렇지 않으면 런타임 에러 발생 가능
    	if(N!=1){
    		dp[2]=2;	
    	}
    	
    	System.out.println(solution(N));
    	
    	
    } // end of Main
    
    
    static int solution(int N) {
    	
    	// 연산된 dp[N]이 아닐 경우에만 진행
    	if(dp[N]==null){
    		// dp[N] = 2xn크기 직사각형을 채우는 방법의 수
    		// solution(N-1) = 2(n-1)크기 직사각형을 채우는 방법의 수 구하기
    		// solution(N-2) = 2x(n-2)크기 직사각형을 채우는 방법의 수 구하기
    		dp[N] = (solution(N-1) + solution(N-2))%10007;
    		
    	}
    	
    	return dp[N];
    } // end of solution
    
} // end of Main