다이나믹 알고리즘_타일 채우기 [2/2]

이번에는 타일이 늘었습니다. 이전글은 1*2 / 2*1 두 개의 타일이 있었는데 이번에는 2*2 타일로 추가해보라고 하네요. 과제는 유투브 '동빈나'님의 알고리즘 강의를 참고했습니다.

 

---

 

별로 달라지는 건 없는 것 같습니다. 수열의 규칙이 바꼈을 뿐.. 규칙을 달리해서 수열을 전개해보라는 걸까요. 일단 이전글처럼 일반 반복문, 재귀함수 버전으로 한 번 작성해보겠습니다.

 

 

---

 

제가 뭔가를 잘 못 생각하고 있는걸까요.. 아무리 고민해봐도 수식에서 숫자 1개 추가하고 1개 바꿔주는 것 외에는 달라지는게 안보이는데 흠.. 일단 미심쩍으므로 재귀함수 버전만 짜보고 강의를 들어보겠습니다.

​

굳이 값을 리턴해야하는 경우가 아니라면 재귀함수에서는 그냥 void함수로 사용하고 포인터를 써서 특정 변수들을 바꿔주는 방식이 더 편리한 것 같습니다. 에러값을 리턴해서 혹시 모를 에러에 대비하고 싶다면 int 타입 함수를 쓰되, 그냥 정상일 경우 0을 리턴해서 0이 아닌 값이 리턴됐을 때 취할 로직을 만들어주면 될 것 같아요.

 

#include <stdio.h>
#define FLOOR 10
void tile_find(int* arr, int i);

void main()
{
	int tile_arr[FLOOR] = { 0 };  // 모두 0으로 초기화
	
	tile_find(tile_arr, FLOOR - 1);

	for (int i = 0; i < FLOOR; i++)
		printf("\n 타일넓이 : 2 * %d, 경우의 수 : %d",
			i + 1, tile_arr[i]);

	printf("\n");
}

void tile_find(int* arr, int i)
{
	if (i < 0)
		return;
	tile_find(arr, i - 1);
	
	if (i == 0)
	{
		arr[i] = 1;
		return;
	}
	if (i == 1)
	{
		arr[i] = 3;
		return;
	}
	arr[i] = arr[i - 1] + 2 * arr[i - 2];
}

 

---

 

아 타일 추가는 그냥 곁다리 추가 설명정도였습니다. 한번 떠 짜볼만한 과제는 아니었네요..ㅎㅎ 그냥 복습한셈 쳐야지..

​

타일 채우기 문제의 경우는 굳이 중요한 알고리즘이라기 보다는 넓이에 따라 맞는 수열의 수식을 짜는게 더 중요한 것 같아 여기까지만 하겠습니다. 수식은 합리적인 방식으로 세우기보다는 경우의 수들을 다 계산해보면서 규칙성을 찾아내는 것이라 수식 자체를 연구할 필요는 없는 것 같아요. 특정 수식을 코드로 구성하는 방법에 더 집중하는 것이 맞는 것 같습니다.