[프로그래머스] level 3 - 타일 장식물

https://programmers.co.kr/learn/courses/30/lessons/43104

코딩테스트 연습 - 타일 장식물 | 프로그래머스

 본 문제는 DP 문제로 분류되어 있지만 메모이제이션 없이도 문제가 해결된다. 

이런 방법으로 타일을 만들 때, n개의 타일의 둘레를 구하는 문제다.

(타일의 개수) : (타일의 둘레)

2 : (2+1) * 2

3 : (3+2) * 2

4 : (5+3) * 2 과 같이 나오는데 일반화를 하면 f(n) = (x+y)*2, f(n+1) = ( (x+y) + x ) * 2로 나타낼 수 있다.

#include <string>
#include <vector>
 
using namespace std;
long long answer;
void cal(long long x, long long y, int cnt, int n) {
    if (cnt == n) {
        answer = (x+y)*2;
        return;
    }
    cal(x+y, x, cnt+1, n);
}
 
long long solution(int N) {
    cal(1, 1, 1, N);
    return answer;
}

 

2020-05-07 추가+)

bottom up 방식

#include <string>
#include <vector>
 
using namespace std;
 
long long d[81][2];
 
long long solution(int N) {
    
    d[1][0] = 1;
    d[1][1] = 1;
    for (int i = 2; i <= 80; i++) {
        long long x = d[i-1][0];
        long long y = d[i-1][1];
        d[i][0] = y;
        d[i][1] = x+y;
    }
    return (d[N][0] + d[N][1])*2;
}