[프로그래머스/java] 2 x n 타일링 - DP

https://programmers.co.kr/learn/courses/30/lessons/12900

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

 

이 문제를 풀 때, 일단 n 에 따른 갯수가 몇개인지 구해봐야한다.

 

n = 1일때, 갯수는 1

n = 2일때, 갯수는 2

n = 3일때, 갯수는 3

n = 4일때, 갯수는 5

n = 5일때, 갯수는 8

 

위의 방식을 따라가다보면 피보나치 수열이 완성된다.

 

int[] arr = new int[n + 1] 로 n+1 만큼 배열의 공간을 잡아준다.

 

arr의 0번째와 1번째에 1을 넣어주고,

 

arr[i] = arr[i-2] + arr[i-1] 로 배열을 반복하며 값을 넣어주면 된다.

 

이때, 제한사항에 1,000,000,007로 나눈 나머지를 구하라했다.

 

이것 때문에 계속 오답이 나왔었는데,

 

arr[i] = ( arr[i-2] + arr[i-1] ) % 1000000007; 로 바꿨더니 정답 처리가 되었다.

 

 

package twoNTiling;

public class TwoNTiling {

	public static void main(String[] args) {
		Solution s = new Solution();
		
		System.out.println(s.solution(4));
	}
}

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