[Kotlin] 프로그래머스 - 3 x n 타일링
Kotlin문제
가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.
- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
가로의 길이 n은 5,000이하의 자연수 입니다.
경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
입출력 예
입력: 4
출력: 11
풀이
n이 홀수이면 타일을 전부 채울 수 없다.
- 직사각형 타일이 가로 크기가 짝수이기 때문에 가로, 세로가 전부 홀수인 바닥은 가득 채울 수 없다.
n=4일 때
- 이전 단계(n=2) 패턴(3가지)을 두 가지씩 조합하여 9가지 패턴을 만들 수 있다.
- 이전 단계에서 나오는 패턴을 조합하여 만들 수 없는 특수 패턴은 2가지이다.
- f(4) = 이전 단계 패턴 조합 + 현재 단계 특수 패턴
- = [2] 전체 패턴 × [2] 전체 패턴 +[4] 특수 패턴
- = f(2) × 3 + 2
n=6일 때
- 이전 단계에서 2칸이 추가되면서 특수 패턴도 2가지가 추가된다.
- 이전 단계 패턴 조합은 [4] 패턴이 왼쪽 × [2] 패턴이 오른쪽, [2] 패턴이 왼쪽 × [4] 패턴이 오른쪽으로 배치되는 두 유형이 있다.
- 다만 한 유형은 [2] 패턴 × [2] 패턴 × [2] 패턴으로 나올 수 있는 조합이 중복되므로 중복 제외 처리를 해야 한다.
- 중복되지 않는 패턴은 특수 패턴과 [2] 패턴이 조합되는 경우로, 앞선 조합이 [4] 전체 패턴 × [2] 전체 패턴이면 나머지 조합은 [2] 전체 패턴 × [4] 특수 패턴만 구하면 된다.
- f(6) = 이전 단계들 패턴 조합 + 현재 단계 특수 패턴
- = [4] 전체 패턴 × [2] 전체 패턴 + [2] 전체 패턴 × [4] 특수 패턴 + [6] 특수 패턴
- = f(n-2) × 3 + f(n-4) × 2 + 2
n=8일 때
- f(8) = [6] 전체 패턴 × [2] 전체 패턴 + [4] 전체 패턴 × [4] 특수 패턴 + [2] 전체 패턴 × [6] 특수 패턴 + [8] 특수 패턴
- = f(n-2) × 3 + f(n-4) × 2 + f(2) × 2 + 2
위에서 찾아낸 규칙으로 점화식을 만들 수 있다.
text
f(n) = f(n-2)×3 + f(n-4)×2 + ... + f(4)×2 + f(2)×2 + 2점화식을 간략화 해보면 다음과 같다.
text
f(n) = f(n-2)×3 + f(n-4)×2 + ... + f(4)×2 + f(2)×2 + 2
// 피보나치 수열의 정의를 활용하여 변환
f(n-4)×2 + ... + f(4)×2 + f(2)×2 + 2
= 2(f(n-4) + ... + f(4) + f(2) + 1)
= f(n-2) - f(n-4)
f(n) = f(n-2)×3 + f(n-2) - f(n-4)
= f(n-2)×4 - f(n-4)코드1. 점화식
- Kotlin
kotlin
class Solution {
fun solution(n: Int): Long {
if (n % 2 != 0) return 0
val dp = LongArray(n + 1)
dp[0] = 1
dp[2] = 3
for (i in 4..n step 2) {
dp[i] = dp[i - 2] * 3
for (j in i - 4 downTo 0 step 2)
dp[i] = dp[i] + dp[j] * 2
dp[i] = dp[i] % 1000000007
}
return dp[n]
}
}- JAVA
java
class Solution {
public long solution(int n) {
if (n % 2 != 0) return 0;
long[] dp = new long[n + 1];
dp[0] = 1;
dp[2] = 3;
for (int i=4; i<=n; i+=2) {
dp[i] = dp[i - 2] * 3;
for (int j = i - 4; j>=0; j = j - 2)
dp[i] += dp[j] * 2;
dp[i] %= 1000000007;
}
return dp[n];
}
}- 정확성 테스트
text
테스트 1 〉 통과 (13.20ms, 74.7MB)
테스트 2 〉 통과 (20.08ms, 76.8MB)
테스트 3 〉 통과 (18.03ms, 78.7MB)
테스트 4 〉 통과 (17.37ms, 80.7MB)
테스트 5 〉 통과 (0.37ms, 73.2MB)
테스트 6 〉 통과 (8.23ms, 78.4MB)
테스트 7 〉 통과 (14.43ms, 73.3MB)
테스트 8 〉 통과 (19.67ms, 81MB)
테스트 9 〉 통과 (18.58ms, 77.7MB)
테스트 10 〉 통과 (4.27ms, 76MB)
테스트 11 〉 통과 (11.33ms, 78MB)
테스트 12 〉 통과 (4.38ms, 74.9MB)
테스트 13 〉 통과 (5.28ms, 76.3MB)
테스트 14 〉 통과 (4.93ms, 77MB)- 효율성 테스트
text
테스트 1 〉 통과 (19.57ms, 51.7MB)
테스트 2 〉 통과 (18.70ms, 52.3MB)
테스트 3 〉 통과 (21.87ms, 52.4MB)
테스트 4 〉 통과 (19.71ms, 52MB)
테스트 5 〉 통과 (19.60ms, 52.3MB)
테스트 6 〉 통과 (20.36ms, 52.3MB)코드 2. 점화식 간략화 + 나머지 연산 분배 법칙
- Kotlin
kotlin
class Solution {
fun solution1(n: Int): Long {
if (n % 2 != 0) return 0
val mod = 1000000007
val dp = LongArray(n + 1)
dp[0] = 1
dp[2] = 3
for (i in 4..n step 2) {
dp[i] = (dp[i - 2] * 4 % mod - dp[i - 4] % mod + mod) % mod
}
return dp[n]
}
}- JAVA
java
class Solution {
public long solution(int n) {
if (n % 2 != 0) return 0;
long[] dp = new long[n + 1];
long 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 dp[n];
}
}- 정확성 테스트
text
테스트 1 〉 통과 (0.19ms, 78.3MB)
테스트 2 〉 통과 (0.24ms, 93.1MB)
테스트 3 〉 통과 (0.29ms, 86.2MB)
테스트 4 〉 통과 (0.29ms, 86.9MB)
테스트 5 〉 통과 (0.05ms, 75.7MB)
테스트 6 〉 통과 (0.17ms, 74MB)
테스트 7 〉 통과 (0.15ms, 73.6MB)
테스트 8 〉 통과 (0.26ms, 76.1MB)
테스트 9 〉 통과 (0.24ms, 73.4MB)
테스트 10 〉 통과 (0.18ms, 75MB)
테스트 11 〉 통과 (0.27ms, 67MB)
테스트 12 〉 통과 (0.18ms, 78.6MB)
테스트 13 〉 통과 (0.12ms, 70.5MB)
테스트 14 〉 통과 (0.17ms, 78.7MB)- 효율성 테스트
text
테스트 1 〉 통과 (0.25ms, 52.6MB)
테스트 2 〉 통과 (0.25ms, 51.5MB)
테스트 3 〉 통과 (0.24ms, 52MB)
테스트 4 〉 통과 (0.24ms, 51.6MB)
테스트 5 〉 통과 (0.27ms, 52MB)
테스트 6 〉 통과 (0.25ms, 51.7MB)
