[BOJ] 백준 #13301. 타일 장식물 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/13301

• 알고리즘 분류: 다이나믹 프로그래밍
• 난이도: Bronze Ⅰ

💬 풀이

이 문제는 너무 대놓고 피보나치 수열이라서 순탄하게 풀…ㅈ줄 알았다..    후.. 공부할 게 천지😊

• 피보나치 수열
• 재귀
• 다이나믹 프로그래밍 (DP)

피보나치 수열의 n번째 항을 재귀적으로 구하면 중복된 연산이 계속 발생해서 $O({1.618}^n)$이 걸린다. 그런데 피보나치 수열을 DP를 이용해서 풀면, 미리 배열을 만들어두고 0번째 인덱스부터 하나씩 채워 나가는 방식으로 해결할 수 있고, n+1칸을 채우고 나면 답을 알 수 있으니 $O(n)$이 걸린다. 이렇게 중간 결과를 저장해서 이용하는지 아닌지에 따라 극적인 시간 복잡도의 차이가 발생한다.

>> DP문제 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

DP는 복잡하려고 하면 한도 끝도 없이 어려워지지만, 코딩테스트에 나올 수준의 DP문제는 일단 점화식만 찾고 나면 그 뒤엔 초기값을 채워넣은 후에 반복문을 돌면서 배열을 채우면 끝이여서 구현이 쉽고 코드도 짤막한 편이다.
[YouTube] (BaaarkingDog, [바킹독의 실전 알고리즘] 0x10강 - 다이나믹 프로그래밍)

1. DP를 이용해 피보나치 수열 구현.     $a_n = a_{n-1} + a_{n-2} (n>3)$
   👉🏻 전역에 dp[] 선언하고, 점화식 이용해서 초기값 주고 for문 돌기
2. 구하고자 하는 직사각형의 둘레는 $2 × (a_n + (a_n + a_{n-1})) = 2(2a_n + a_{n-1})$
3. long long 주의^^

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

long long dp[81];

int main() {
	//freopen("input.txt", "rt", stdin);
	int N;
	cin >> N;
	
	dp[1] = 1; dp[2] = 1;
	for (int i = 3; i <= N; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	long long perimeter = 2 * (2 * dp[N] + dp[N - 1]);
	cout << perimeter << endl;

	return 0;
}