[프로그래머스] [백준 11726] 2 x n 타일링

문제

---

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

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

2 x 5 의 예

 

 

 

풀이

---

https://programmers.co.kr/learn/courses/30/lessons/12900?language=java 

코딩테스트 연습 - 2 x n 타일링

해당 문제는 프로그래머스에도 존재한다.

 

풀이는

문제 개수를 세봤다.

1 -> 1

2 -> 2

3 -> 3

4 -> 5

5 -> 8

6 -> 13

7 -> 21  

  ...

어떠한 규칙이 보이는가

dp[n] = dp[n-1] + dp[n-2] 라는 피보나치 수열과 비슷한 규칙이 나온다.

dp[n-1]

 

dp[n-2]

 

이렇게 두가지경우가 성립하기 때문에 위와 같은 규칙이 나온다.

 

이 방식을 적용하돼 문제에서 원하는 답이 10,007로 나눈값이므로

 

dp[n] = (dp[n-1] + dp[n-2]) % 10007 을 사용하면 된다.

 

 

<코드>

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

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    
	    int n = Integer.parseInt(bufferedReader.readLine());
		
	    int[] dp = new int[1001];
	    dp[0] = 0;
	    dp[1] = 1;
	    dp[2] = 2;

	    for(int i = 3; i <= n; i++){
	    	dp[i] = dp[i-1] + dp[i-2];
	    	dp[i] %= 10007;
	    }
	    
	    System.out.println(dp[n]);
	}
}

int[] dp = new int[n+1] 로 했을때 런타임 에러가 떴다.. 이유는 나도 잘 모르겠다.

여기서 n 은 1000까지라고 정의를 해줬기 때문에 int[1001] 로 배열크기를 정의했더니 맞았다.

 

<프로그래머스 코드>

class Solution {
    
    static int[] dp;
    public int solution(int n) {
        int answer = 0;
        
        dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i = 3 ; i <= n ; i++){
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        
        answer = dp[n];
        return answer;
    }
}