문제출처: https://programmers.co.kr/learn/courses/30/lessons/12902#
문제 설명
가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다
- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우
예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 가로의 길이 n은 5,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
class Solution {
int divisor = 1000000007;
public int solution(int n) {
//큰 수를 다룰것이기 때문에 long 타입을 사용
long[] dp = new long[n + 1];
long add = 0;
dp[0] = 1;
dp[2] = 3;
if (n == 2) return 3;
if (n % 2 == 1) return 0;
for (int i = 4; i <=n; i+= 2) {
add += dp[i-4] * 2;
dp[i] = dp[i-2] * 3 + add;
// 값이 너무 커질 경우를 대비한 modulo
dp[i] = dp[i] % divisor;
add = add % divisor;
}
return (int) dp[n];
}
}내 풀이는 위와 같다. 처음에는 Brute-force 알고리즘으로 모든 경우의 수를 재귀적으로 계산하는 방식으로 풀었다가 당연하게도 시간초과가 나서 DP를 통해 풀었다. 그래도 Brute-force 방식으로 푼 코드를 통해 n이 작을 경우의 답들을 구할수 있어서 그 값들을 통해 수열의 패턴을 더 쉽게 구할수 있었다.
위 코드를 간단히 설명하자면, 우선 n이 홀수일 경우에는 직사각형을 가득 채우는 방법이 없기 때문에 0을 리턴한다. 그리고 dp[i]의 값은 dp[i-2]의 값에 3을 곱한후에 추가로 dp[0] 부터 dp[i-4] 까지의 값을 합한 값에 2를 곱한후 더해준다. 3을 곱하는 이유는 길이가 2인 직사각형을 채울수 있는 경우의 수가 3가지가 있기 때문에 이전 케이스에서 3을 곱해주는 것이고 추가로 더해주는 값은 이웃과 작대기를 공유하는 경우를 계산한 값이다.
