백준 13301 - 타일 장식물

문제

알고리즘 분류)

• 수학
• 다이나믹 프로그래밍

이번에도 점화식을 중점적으로 메모이제이션을 이용해 구현하는 dp문제중 쉬운난이도다
1번째 사각형의 둘레는 4이다 -> 그것은 [1,1,1,1]의 합으로 나타낼 수 있다
2번째 사각형의 둘레는 [1,1,2,2] = 6
3번째 사각형의 둘레는 [2,2,3,3] = 10
4번째 사각형의 둘레는 [3,3,5,5] = 16
그렇다면
N번째 사각형의 둘레는

[N-1변의길이, N-1변의길이, N-1짧은 변의길이+N-1긴 변의길이, N-1짧은 변의길이+N-1긴 변의길이] 이다

소스코드

python)

N = int(input())
dp = [[0 for col in range(4)] for row in range(N)]
dp[0]=[1,1,1,1]

for i in range(1,N):
    dp[i][0]=dp[i][1]=dp[i-1][3]
    dp[i][2]=dp[i][3]=dp[i-1][1]+dp[i-1][3]
    
print(sum(dp[N-1]))

java script)

let N = parseInt(require("fs").readFileSync("/dev/stdin").toString());

const dp = new Array(80).fill(0);
dp[0] = 4n; //BigInt를 사용
dp[1] = 6n;

for (let i = 2; i < 80; i++) dp[i] = dp[i - 2] + dp[i - 1];

console.log(dp[N - 1].toString());

-> 더 단순한 점화식을 사용