๋ฌธ์ ๋งํฌ
์ฝ๋ฉํ ์คํธ ์ฐ์ต - 2 x n ํ์ผ๋ง
๊ฐ๋ก ๊ธธ์ด๊ฐ 2์ด๊ณ ์ธ๋ก์ ๊ธธ์ด๊ฐ 1์ธ ์ง์ฌ๊ฐํ๋ชจ์์ ํ์ผ์ด ์์ต๋๋ค. ์ด ์ง์ฌ๊ฐํ ํ์ผ์ ์ด์ฉํ์ฌ ์ธ๋ก์ ๊ธธ์ด๊ฐ 2์ด๊ณ ๊ฐ๋ก์ ๊ธธ์ด๊ฐ n์ธ ๋ฐ๋ฅ์ ๊ฐ๋ ์ฑ์ฐ๋ ค๊ณ ํฉ๋๋ค. ํ์ผ์ ์ฑ์ธ ๋๋
programmers.co.kr
์ ๊ทผ ๋ฐฉ๋ฒ
์ฒ์์ n์ด ํ์์ธ ๊ฒฝ์ฐ, ์ง์์ธ ๊ฒฝ์ฐ๋ฅผ ๋๋ ์
์์ด ๋ฐฉ์์ผ๋ก ์ ๊ทผํ์๋ค.
๊ฐ๋ก์ ๊ธธ์ด๊ฐ 8์ธ ํ์ผ์ 8P8 + 7P6 + 6P4 + 5P2 + 4P0์ด๊ณ
๊ฐ๋ก์ ๊ธธ์ด๊ฐ 7์ธ ํ์ผ์ 7P7 + 6P5 + 5P3 + 4P1์ด๊ธฐ ๋๋ฌธ์
ํ์ง๋ง n์ ๋๋ฌด ๋ฒ์๊ฐ ๋๊ณ ํจ์จ์ฑ์ด ๋ฎ์ factorial์ ์ฌ์ฉํด์ ํต๊ณผ๋ฅผ ํ์ง ๋ชปํ์๋ค. (๋ฎ์ ์์์๋ ์ ๋๋ก ํ์ผ์ ์๋ฅผ ์ฐพ๊ธด ํ์๋ค.)
๊ทธ๋์ ๋ค์ ๋ฌธ์ ๋ฅผ ์ดํด๋ณด๋
1์ผ๋ 1P1 = 1
2์ผ๋ 2P2 + 1P0 = 2
3์ผ๋ 3P3 + 2P1 = 3
4์ผ๋ 4P4 + 3P2 + 2P0 = 5
5์ผ๋ 5P5 + 4P3 + 3P1 = 8
[n] = [n-1] + [n-2] ๋ผ๋ ํน์ง์ ๊ฐ๊ณ ์์๋ค.
๊ทธ๋์ dp ๋ฐฉ์์ผ๋ก ์ ๊ทผํ์๋ค.
์ฃผ์์
n์ด 60000๊น์ง์ ํฐ ๋ฒ์๋ฅผ ๊ฐ๋๋ค.
๋๋ฌธ์ ๋ฌธ์ ์ ์กฐ๊ฑด์์๋ ๋์ถ๊ฐ answer์ 1000000007์ ๋๋ ๋๋จธ์ง ๊ฐ์ ๊ตฌํ๋ผ ํ์๋๋ฐ,
์ต์ข ์ ์ธ ๊ฐ answer์ 1000000007์ %ํ๋ฉด ๋ต์ ๊ตฌํ ์ ์๋ค.
for(let i = 2; i < n; i++){ dp[i] = (dp[i-1] + dp[i-2]) % 1000000007; }
์ด์ฒ๋ผ ์ค๊ฐ์ for๋ฌธ์์ ์ฒ๋ฆฌํด ์ค์ผ ํ๋ค.
// dp ์ฝ๋
function solution(n) {
var answer = 0;
let dp = new Array(n).fill(0);
dp[0] = 1;
dp[1] = 2;
for(let i = 2; i < n; i++){
dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
}
answer = dp[n-1]
return answer;
}
// ์์ด์ ์ฌ์ฉํ ํ์ด
function solution(n) {
var answer = 0;
if(n % 2 === 0){
for(let oneLenTile = n, totalTile = n; oneLenTile >= 0; oneLenTile -= 2, totalTile--){
answer += permutation(totalTile, oneLenTile)
}
}else{
for(let oneLenTile = n, totalTile = n; oneLenTile > 0; oneLenTile -= 2, totalTile--){
answer += permutation(totalTile, oneLenTile)
}
}
return answer % 1000000007;
}
const factorial = (num) => {
if(num === 0) return 1;
return num * factorial(num - 1)
}
const permutation = (num1, num2) => {
return factorial(num1) / (factorial(num2) * factorial(num1 - num2))
}
'์ฝ๋ฉํ ์คํธ > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Javascript] ๋ ๋ฐ๋จน๊ธฐ (12913) (0) | 2022.06.23 |
---|---|
[Javascript] ํผ๋ก๋ (87946) (0) | 2022.06.23 |
[Javascript] ๊ฐ์ฅ ํฐ ์ ์ฌ๊ฐํ (12905) (0) | 2022.06.22 |
[Javascript] ์ด์ง ๋ณํ ๋ฐ๋ณต (70129) (0) | 2022.06.20 |
[Javascript] ์ฌ๋ฐ๋ฅธ ๊ดํธ (12909) (0) | 2022.06.19 |