🎯문제
가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다
- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우
예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 가로의 길이 n은 5,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
입출력 예
| n | result |
|---|---|
| 4 | 11 |
입출력 예 설명
입출력 예 #1
다음과 같이 11가지 방법이 있다.
✏️풀이
코드
class Solution {
public int solution(int n) {
// dp 배열
long[] dp = new long[n+1];
// 나누는 수
int mod = 1000000007;
// 초깃값 설정
dp[0] = 1;
dp[2] = 3;
// 반복문 진행
for(int i = 4; i <= n; i += 2)
dp[i] = (dp[i-2] * 4 % mod - dp[i-4] % mod + mod) % mod;
return (int)dp[n];
}
}설명
dp의 방식으로 진행하였다.
규칙을 찾아서 규칙에 맞게 계산을 한 뒤에 원하는 값을 출력하면 되는 방식이다.
dp 배열의 크기는 n+1로 주어서 n까지 계산이 가능하도록 한다. mod라는 변수에 나눠야하는 값을 저장한다.
반복문을 진행하는데, 점화식은 dp[i] = dp[i-2] * 4 - dp[i-4] 가 된다. 그러나 i는 모든 값이 아닌 짝수에서만 해당이 된다. 따라서 2, 4, 6, 8 ... 처럼 짝수만 계산을 할 수 있도록 i += 2 라는 증감식을 사용한다.
우리는 값을 나누어서 계산을 진행해야하기 때문에 모듈러 분배규칙을 사용해주어야한다.
모듈러 분배규칙
- (A + B) % M = ((A % M) + (B % M)) % M
- (A x B) % M = ((A % M) x (B % M)) % M
- (A - B) % M = ((A % M) - (B % M) + M) % M
위의 모듈러 분배규칙을 사용해서 반복해서 계산하고 반복문이 종료된 뒤에 dp[n]의 값을 int형으로 형변환을 시켜준 뒤 반환하면 문제를 해결할 수 있다!
💡느낀 점
기존에 2 x n 타일링 문제를 푼 적이 있었기 때문에 규칙을 찾아야 한다는 것이나 짝수에서만 찾을 수 있다는 조건들은 금방 알아챌 수 있었다. 그러나 실제 점화식을 세우는 부분에서 헷갈렸고 다른 블로그들을 참고해서 입출력 예시들을 사용해 점화식을 세울 수 있었다. 또한 모듈러 분배규칙을 처음 알고 사용하였는데 같은 유형의 문제라도 쉽지 않구나란 생각이 들게 만드는 문제였다..
링크
