< 백준 BaekJoon : 1904번 01타일> C++

<< 문제 >> 

https://www.acmicpc.net/problem/1904

1904번: 01타일

 

00과 1을 조합해서 만들어낼 수 있는 경우의 수를 알아내는 문제입니다.

 

사실 모든 경우의 수라서 백트래킹으로 생각할 수도 있지만 Dynamic Programming으로 해결해야 하는 문제입니다. 

 

그런데 사실 피보나치 수열이라 굳이 DP로 하지 않아도 해결할 수 있습니다. 

 

피보나치 수열인 것만 깨닫게 되면 크게 어렵지는 않았네요.

 

 

<< 코드 >> 

 

#include <iostream>
using namespace std;

int main() {

	int num;
	cin >> num;

	int* arr = new int[num+1];

	arr[0] = 1;
	arr[1] = 1;

	for (int i = 2; i <= num; i++) {
		arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
		
	}
	cout << arr[num];

	delete[] arr;
}

 

<< 깃헙 >>

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/1904.%E2%80%8501%ED%83%80%EC%9D%BC