[Programmers] 258705번 - 산 모양 타일링 [Java][C++]
1. 아이디어
주어진 도형을 정삼각형 또는 마름모 타일을 활용해서 채울 수 있는 경우의 수를 구하는 문제로 다이나믹 프로그래밍을 활용하면 해결할 수 있다. dp 테이블은 윗변의 길이를 i라 할때 dp[i]는 윗변의 길이가 i인(왼쪽부터 i만큼만) 해당 도형을 채울 수 있는 경우의 수로 정의하면 된다. 마름모 타일의 경우 간섭이 존재할 수 있어서 실제로는 2차원 dp 테이블로 설정해서 dp[i][0]은 오른쪽 끝 타일이 삼각형인 경우, dp[i][1]은 오른쪽 끝 타일이 마름모인 경우로 정의했다.
이러면 dp[0][0]은 정삼각형 타일 하나로만 채울 수 있으므로 1이 되며 dp[0][1]은 정삼각형 하나로만 채울 수 있어서 끝이 마름모 타일이 될 수 없기 때문에 0이 된다.
아래 그림이 그 예시로 정삼각형 하나만 존재하는 도형에서는 dp[0][0] = 1, dp[0][1] = 0임을 알 수 있다. 윗변의 길이가 1인 경우는 윗변에 삼각형이 없는 경우와 있는 경우 아래와 같은 타일링들이 나올 수 있다. 윗변의 길이가 1이면서 윗변에 삼각형이 없는 경우 타일링은 총 3가지가 가능하며 오른쪽 끝 타일이 정삼각형 타일인 경우 2가지, 마름모인 경우 1가지가 존재하며, 윗변에 삼각형이 있는 경우 타일링은 총 4가지로 오른쪽 끝 타일이 정삼각형이 경우 3가지, 마름모인 경우 1가지가 존재하게 된다.
윗변의 길이가 i인 도형에 대해 윗변의 길이가 i+1 도형의 타일링은 오른쪽에 어떻게 배치하느냐로 타일링의 수를 구할 수 있다. 이전 타일링의 오른쪽 끝 타일이 정삼각형인 경우와 마름모인 경우 이에 대응하는 다음 타일링 조합은 아래와 같다.
위 사진을 통해 규칙성을 발견할 수 있는데 윗변에 정삼각형이 없는 경우는 총 5가지 타일링을 고려해볼 수 있다. 아래 사진의 위쪽 3개의 타일링은 현재 타일링의 오른쪽 끝을 정삼각형 타일로 끝낼 수 있는 경우이고 아래 2개의 타일링은 현재 타일링의 오른쪽 끝을 마름모 타일로 끝낼 수 있는 경우이다.
- 첫 번째 타일링은 이전 타일링의 오른쪽 끝이 정삼각형 타일로 끝난 경우만큼 존재한다.
- 두 번째 타일링은 이전 타일링의 오른쪽 끝이 정삼각형 타일로 끝난 경우에서 해당 오른쪽 끝 타일과 현재 타일링의 타일을 마름모로 고려한 경우로 이전 타일링의 오른쪽 끝이 정삼각형 타일로 끝난 경우만큼 존재한다.
- 세 번째 타일링은 이전 타일링의 오른쪽 끝이 마름모 타일로 끝난 경우만큼 존재한다.
- 네 번째 타일링은 이전 타일링의 오른쪽 끝이 정삼각형 타일로 끝난 경우만큼 존재한다.
- 다섯 번째 타일링은 이전 타일링의 오른쪽 끝이 마름모 타일로 끝난 경우만큼 존재한다.
따라서 윗변에 정삼각형이 없는 경우 dp[i][0] = 2 * dp[i-1][0] + dp[i-1][1], dp[i][1] = dp[i-1][0] + dp[i-1][1]이 됨을 알 수 있다.
윗변에 정삼각형 타일이 존재하는 경우도 마찬가지로 경우를 분류하면 dp[i][0] = 3 * dp[i-1][0] + 2 * dp[i-1][1], dp[i][1] = dp[i-1][0] + dp[i-1][1]이 됨을 알 수 있다.
2. 복잡도
| 시간복잡도 | 공간복잡도 |
|---|---|
| $O(N)$ | $O(N)$ |
$N$ =
n(=tops.length, 사다리꼴 층수)
3. 코드
풀이 [Java][C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
static int MOD = 10007;
public int solution(int n, int[] tops) {
int[][] dp = new int[1 + n][2];
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
if (tops[i] == 0) {
dp[i + 1][0] = (2 * dp[i][0] + dp[i][1]) % MOD;
} else {
dp[i + 1][0] = (3 * dp[i][0] + 2 * dp[i][1]) % MOD;
}
dp[i + 1][1] = (dp[i][0] + dp[i][1]) % MOD;
}
return (dp[n][0] + dp[n][1]) % MOD;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
const int MOD = 10007;
int dp[1 + 100000][2];
int solution(int n, vector<int> tops) {
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
if (tops[i] == 0) {
dp[i + 1][0] = (2 * dp[i][0] + dp[i][1]) % MOD;
} else {
dp[i + 1][0] = (3 * dp[i][0] + 2 * dp[i][1]) % MOD;
}
dp[i + 1][1] = (dp[i][0] + dp[i][1]) % MOD;
}
return (dp[n][0] + dp[n][1]) % MOD;
}