프로그래머스_연습문제_2xn타일링

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

프로그래머스

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한 사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

 

문제 풀이

처음에는 단순하게 가로로 놓았을 때, 세로로 놓았을 때만을 고려해서 문제를 풀었는데 6만이하라는 입력때문에 시간초과가 발생했었다.

그래서 손으로 일일히 그려가며 경우의 수를 찾고 있었는데, 모양새가 피보나치의 수와 완전 판박이여서 피보나치 알고리즘처럼 메모이제이션을 해가며 문제를 풀어보니 통과되었다.

또한, 제한 사항 2번째에 1,000,000,007로 나누어 준다는 사항이 있는데, 메모이제이션을 해가며 경우의 수를 구하고 마지막에 나누면 이미 숫자가 변해버린 뒤여서 제대로 된 값이 나오지 않았다. 그래서 메모이제이션을 하는 도중 매번 나누어서 값을 저장했다.

풀이 코드

class Solution {
		// dp 담을 배열 선언
	    static long[] dp;
	    public long solution(int n) {
	    	//정답 answer
	        long answer = 0;
	        // dp 배열의의 사이즈는 주어지는 숫자 n + 1 
	        dp = new long[n+1];
	        answer = dp_memoization(n);
	        return answer;
	    }
	    // 메모이제이션 메서드
	    public long dp_memoization(int n)
	    {
	    	// 만약 n이 3 미만이면 그냥 그대로 return.
	        if(n < 3) return n;
	        // 만약 n이 이미 계산 되어 있는 수라면.
	        if(dp[n]!=0)
	        {
	        	// dp[n] 리턴
	            return dp[n];
	        }
	        // 피보나치 알고리즘 수행
	        dp[n] = dp_memoization(n-1) + dp_memoization(n-2);
	        // 나머지를 해서 저장해야 값이 변하기 전에 담을 수 있음.
	        dp[n] = dp[n] % 1000000007;
	        // dp[n] 리턴
	        return dp[n];
	    }
	}