백준) 2 x n 타일링 (재귀함수) / JAVA

문제 출처입니다.

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

11726번: 2×n 타일링

 

사고의 흐름

2x1 타일링을 할 때부터 차례대로 하여 규칙을 찾아내보록 한다.

그 결과, 2x1일때는 1, 2x2 일때는 2, 2x3 일때는 3, 2x4 일때는 5, 2x5 일대는 8이라는 결과가 나온다. 그런데 2x5 타일링을 분석하면 다음 그림과 같다.

 

↑↑↑↑  2x3 타일리에 가로 타일 2개를 붙여 2x5 타일링을 완성한 경우

 

↑↑↑↑  2x4 타일리에 세로 타일 1개를 붙여 2x5 타일링을 완성한 경우

즉, 5번째 타일링은 3번째와 4번째 타일링을 더한 값이다. 즉 피보나치 수열로 나타낼 수가 있다. 

 

해결방법

package backjoon;
import java.util.*;
 
public class Beak11726{
 
    public static void main(String[]args){
        Scanner scan=new Scanner(System.in);
        System.out.println("n을 입력하세요 n :");
        int n=scan.nextInt();//몇 번째 타일링 개수를 구할 것인지 입력
        int []d=new int[n+1];
 
        d[1]=1;
        if(n>=2) 
        d[2]=2;
        //첫 번째와 두 번째는 피보나치 수열로 만들 수 있는 결과가 아니므로 기본값으로 설정
 
        for(int i=3;i<=n;i++){
            d[i]=d[i-1]+d[i-2]%10007;
        }
        //재귀함수를 이용해서 n=5 일때를 구할경우 d[3]과 d[4]를 순서대로 구한뒤 그 합을 d[5]에 대입. 
 
        System.out.println("2 x n 크기의 직사각형을 채우는 방법의 수 :"+d[n]);
    }
}

결과

의견

매우 쉬운 문제이지만 사소한 부분에 발을 걸려 문제를 풀지 못하였다.

 

동그라미를 친 부분이 헷갈렸던 부분인데 

첫 번째 부분에서 왜 n+1인지 궁금하였다. 

1) n+1대신 1000이라는 넉넉한 숫자를 넣었을 경우

성립

2) n+1 대신 n을 넣었을 경우

예외 발생

>> 즉, 배열을 생성할 땐 배열의 크기를 넉넉하게 하는 것이 도움이 된다!

 

그리고 두 번째 부분이다. 

조금 헷갈리긴 하였지만 당연한 단계였으며 이 부분은 재귀함수가 익숙해지면 극복할 수 있을 것 같다.