문제 출처
나의 풀이
다른 풀이
n이 홀수면 조합이 불가능하므로 무조건 0을 return한다.
n이 짝수일 때만 경우의 수를 고려하면 된다.
n==2일 때를 하나의 단위로 설정했을 때 경우의 수가 2가지로 분류된다.
(1) 일반 경우의수 : 단위 1개 내부에서의 경우의 수 ⇒ *3
(2) 특수 경우의수 : 단위 2개 이상 겹쳐놔야 발생하는 경우의 수 ⇒ *2
======= (1)단위 1개 내부에서의 경우의 수 =======
세로의 길이는 3으로 고정이므로
각 n==2를 하나의 단위로 생각하면 각 단위마다 경우의 수는 3가지가 된다.
n이 증가할수록 곱으로 늘어난다. dp[i] = dp[i-1]*3
⇒⇒ 즉, (1)번 경우의 수는 계속해서 *3으로 늘어난다.
[1] => 가로(1x2) 3개
[2] => 세로(2x1) 2개 + 가로(1x2) 1개
[3] => 가로(1x2) 1개 + 세로(2x1) 2개======= (2)단위 2개 이상 겹쳐놔야 발생하는 경우의 수 =======
그리고 n=4일 때의 예시를 보면 경우의 수 2개가 더 추가된다.
단위 1개(n==2) 2개에 겹쳐서 연결되어 배치되는 경우이다.
그러므로 각 경우의 수는 dp[i] = dp[i-1]*3 + 2가 된다.
여기서 끝나는 게 아니다.
n=4 이상일 때를 고려해보면 (2)번 경우의 수가 중복되는 경우를 고려해야 한다.
let i일 때 dp[i] = dp[i-1]*3 + 2에서
+2가 되는 경우도 계속해서 쌓이므로
⇒⇒ (2)번 경우의 수도 *2로 계속 쌓인다.
이 경우의 수를 고려해주기 위해 그전까지의 값을 for j로 순회해서 *2를 계산해준다.
단순히 이렇게만 고려하면
dp[n] = dp[n-2]*3 + 2 ... 이런 식으로 작성해야 하지만
홀수는 무조건 0이므로 아예 처음부터 짝수로 구성된 배열 dp를 만들면 된다.
참고
(number) >> (count) : (number)를 (count)번 2로 나누기
(number) << (count) : (number)를 (count)번 2로 곱하기
function solution(n) {
const dp = [0, 3, 11];
const idx = n >> 1;
if (n%2 !== 0) return 0
if (idx < 3) return dp[idx]
for (let i=3; i<=idx; i++) {
dp[i] = dp[i-1]*3 + 2;
for (let j=1; j<i-1; j++) {
dp[i] += dp[j] * 2;
}
dp[i] %= 1000000007;
}
return dp[idx];
}
console.log(solution(4)) // 11다른 풀이 2
애초에 +2를 따로 더하지 않고 한번에 *3와 *2를 계산해줘도 된다.
function tiling(n) {
var answer = 0;
let l = [1, 2];
for (let i = 2; i <= n; i++) {
if (i % 2 === 0) {
l.push((l[i - 1] + l[i - 2]) % 100000);
} else {
l.push((2 * l[i - 1] + l[i - 2]) % 100000);
}
}
return (n % 2 === 0) ? l[n] : 0;
}참고
