[Kotlin] 프로그래머스 - 3 x n 타일링
문제
가로 길이가 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
위에서 찾아낸 규칙으로 점화식을 만들 수 있다.
Plain Text
1
f(n) = f(n-2)×3 + f(n-4)×2 + ... + f(4)×2 + f(2)×2 + 2점화식을 간략화 해보면 다음과 같다.
Plain Text
1
2
3
4
5
6
7
8
9
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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];
}
}정확성 테스트
Plain Text
1
2
3
4
5
6
7
8
9
10
11
12
13
14
테스트 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)효율성 테스트
Plain Text
1
2
3
4
5
6
테스트 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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];
}
}정확성 테스트
Plain Text
1
2
3
4
5
6
7
8
9
10
11
12
13
14
테스트 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)효율성 테스트
Plain Text
1
2
3
4
5
6
테스트 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)
[결혼 준비] 스튜디오 업체 선정
결혼준비 스튜디오 업체 선정
Review
[Kotlin] 프로그래머스 - 최댓값과 최솟값
프로그래머스 코딩테스트 문제 최댓값과 최솟값 코틀린 풀이
Kotlin