[백준 11726번 : 실버3] 2xn 타일링 (DP/Java)

이번 문제는 기본적인 DP를 물어보는 문제였다.

사실 처음에 어떻게 풀어야 하나 싶었는데 1부터 한번 방법의 수를 확인해보니

피보나치와 같은 결과가 나온다는걸 알고 금방 풀수 있었다.

 

 

그럼 이제 문제를 살펴보자.

 

 

문제

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

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

입력

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

출력

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

 

 

 

 

 

문제 접근 방법

일단 이번 문제는 시간제한을 되게 1초 준거보면 일단 시간을 최대한 줄여야 한다.

시간을 줄일수 있는 방법에는 이분탐색, DP가 있는데 나는 이번 알고리즘이 DP관련 문제라서 DP로 풀었다.

그리고 지금 생각해보면 총 방법의 수를 찾는것이기 때문에 DP를 쓰는게 맞는것 같다.

 

일단 DP로 접근한다고 하면 우리는 1부터 값이 어떻게 나오는지 확인해봐야 한다.

 

n = 1

방법의 수 : 1

 

n = 2

방법의 수 : 2

 

n = 3

방법의수 : 3

 

n = 4

방법의수 : 5

 

이렇게 쭉 나온다.

나는 여기서 피보나치처럼 n의 방법의 수는 n-1 방법의수 + n-2 방법의 수 라는것을 알게 되었다.

 

따라서 이번 문제는 피보나치와 같은 방식으로 문제를 풀었다.

피보나치에 관한 자세한 설명은 아래 링크에 나와 있으니 확인해보면 될것같다.

https://wpioneer.tistory.com/120?category=1023663 

[자료구조] 동적계획법 알고리즘 ( Dynamic Algorithm)

 

 

아 그리고 이번 문제에서 주의할점은 10007로 나누는것이다.

이번 문제에서 10007로 나눈 나머지를 입력하라고 되어 있는데

dp[]에도 10007로 나눈 나머지를 입력해야한다.

 

전체 소스

import java.util.Scanner;

public class Run {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Run a = new Run();
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] dp = new int[n+1];
		int answer = a.fibo(n,dp);
		answer%=10007;
		System.out.println(answer);
	}

	public int fibo(int n, int[] dp) {
		// TODO Auto-generated method stub
		if(dp[n] == 0) {//만약에 dp[n]이 비어 있다면 진입
			if(n == 1) {
				dp[n] = 1%10007; 
				return dp[n];
			}else if(n == 2) {
				dp[n] = 2%10007;
				return dp[n];
			}else {
				return dp[n] = (fibo(n-1,dp) + fibo(n-2,dp))%10007;
			}
		}else {
			return dp[n];
		}
	}
}

 

 

느낀점

1. DP는 1부터 접근해서 값을 저장하는 방식으러 생각해봐라.