백준 14852번 타일채우기3 C++ 구현해보기

---

```

백준 14852번 타일채우기3 C++ 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 14852 번 풀이
2.  간단한 DP 및 std::array 연습

---

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

14852번: 타일 채우기 3

 

 

백준 14852번 타일채우기는 

난이도 중급 등급의 문제로서

 

2 X N 벽이 주어질때 

 

2 X 1, 1 X 2, 1 X 1 타일로 채우는 경우의 수를 구하는 문제입니다.

 

벽의 너비 N은 1 이상 1,000,000 이하이며

 

입력을 받고

 

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력하면 됩니다.

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

일단 저는 이문제를 보고

 

벽을 채워나간다는 느낌으로 공책에 몇가지 경우의 수를 그려보고

 

DP 문제라는 것을 알게 되었습니다.

 

DP는 동적 프로그램(Dynamic Programming)의 약자입니다.

 

(대표적으로는 KnapSack 문제가 있습니다)

 

각 경우에서 그 경우에 자식의 경우까지 전부 구하면 되는 문제입니다만

 

경우의 수가 클 경우 이를 해결하기 위해

 

memoization 기법을 많이 씁니다.

 

---

자 다시 문제로 돌아와서

 

일단 한줄만 남은 경우

 

혹은 남은 길이가 0 또는 미만 일 경우에는

 

경우에 수를 계산해 아래와 같이 반환값을 설정해주었습니다.

 

		// 남은 길이 1 이하
		if (width <= 1)
		{
			if (width == 1)
			{
				// 위아래 모두 빈 경우
				if ((topIsempty == true) && (bottomIsempty == true))
				{
					retVal = 2;
				}
				// 둘다 찬 경우
				else if ((topIsempty == false) && (bottomIsempty == false))
				{
					retVal = 0;
				}
				// 위아래 중 하나만 빈 경우
				else
				{
					retVal = 1;
				}
			}
			else if (width == 0)
			{
				// 위아래 모두 빈 경우
				if ((topIsempty == true) && (bottomIsempty == true))
				{
					retVal = 1;
				}
			}
			else
			{
				retVal = 0;
			}
		}

 

그 외에 경우에는 

메모아이제이션 테이블에 값이 있으면

그 값을 리턴해주고

 

아닐 경우

경우의 수를 계산해주었습니다.

 

 

 

둘다 빈 경우 5가지 경우를 찾았고

 

한쪽만 빈 경우 2가지 경우

 

그리고

 

두 쪽 다  찬 경우 다음 칸으로 넘어 갔습니다.

 

 

둘다 빈 경우에는 경우가 비슷한 것들이 있어서

병합했습니다.

		else if (wallMemoization[width][topIndex][bottomIndex] != -1)
		{
			retVal = wallMemoization[width][topIndex][bottomIndex];
		}
		else
		{

			if ((topIsempty == true) && (bottomIsempty == true))
			{
				// ▣
				// ▣
				// 2 x 1
				// 1 x 1 - 1 x 1
				retVal += (dp((width - 1), isEmpty, isEmpty)) * 2;

				// ▣
				// ▣▣
				// 2 x 1 - 1 x 1
				// 1 x 1 - 2 x 1
				retVal += (dp((width - 1), isEmpty, isfilled)) * 2;

				// ▣▣
				// ▣▣
				// 1 x 2 - 1 x 2
				retVal += (dp((width - 2), isEmpty, isEmpty));
			}

			else if (((topIsempty == true) && (bottomIsempty == false)) ||
				((topIsempty == false) && (bottomIsempty == true)))
			{

				// ▣
				// ▣
				// 1 x 1

				// ▣
				// ▣▣
				// 1 x 2

				// 1 x 1
				retVal += (dp((width - 1), isEmpty, isEmpty));
				// 1 x 2
				retVal += (dp((width - 1), isEmpty, isfilled));
			}


			//둘다 찬 경우
			else
			{
				// ▣
				// ▣
				// 1 x 1
				retVal += (dp((width - 1), isEmpty, isEmpty));
			}
			retVal = retVal % 1000000007;
			wallMemoization[width][topIndex][bottomIndex] = retVal;
		}

 

 

전체 코드는 다음과 같습니다

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>

class CTile
{
private:
	std::array<std::array<std::array<long long, 2>, 2>,1000002> wallMemoization;
	int32_t wallWidth;


public:
	CTile()
	{
		wallWidth = 0;
		wallMemoization.fill({ {{-1,-1},{-1,-1}} });
	}
	~CTile()
	{

	}

	void setWallWidth(const int32_t _wallWidth)
	{
		this->wallWidth = _wallWidth;
	}

	void printNumberOfCases()
	{
		std::cout << dp(wallWidth, true, true);
	}

	long long dp(int32_t width, bool topIsempty, bool bottomIsempty)
	{
		long long retVal = 0;
		const int32_t topIndex = topIsempty ? 1 : 0;
		const int32_t bottomIndex = bottomIsempty ? 1 : 0;
		const bool isfilled = false;
		const bool isEmpty = true;

		// 남은 길이 1 이하
		if (width <= 1)
		{
			if (width == 1)
			{
				// 위아래 모두 빈 경우
				if ((topIsempty == true) && (bottomIsempty == true))
				{
					retVal = 2;
				}
				// 둘다 찬 경우
				else if ((topIsempty == false) && (bottomIsempty == false))
				{
					retVal = 0;
				}
				// 위아래 중 하나만 빈 경우
				else
				{
					retVal = 1;
				}
			}
			else if (width == 0)
			{
				// 위아래 모두 빈 경우
				if ((topIsempty == true) && (bottomIsempty == true))
				{
					retVal = 1;
				}
			}
			else
			{
				retVal = 0;
			}
		}
		else if (wallMemoization[width][topIndex][bottomIndex] != -1)
		{
			retVal = wallMemoization[width][topIndex][bottomIndex];
		}
		else
		{

			if ((topIsempty == true) && (bottomIsempty == true))
			{
				// ▣
				// ▣
				// 2 x 1
				// 1 x 1 - 1 x 1
				retVal += (dp((width - 1), isEmpty, isEmpty)) * 2;

				// ▣
				// ▣▣
				// 2 x 1 - 1 x 1
				// 1 x 1 - 2 x 1
				retVal += (dp((width - 1), isEmpty, isfilled)) * 2;

				// ▣▣
				// ▣▣
				// 1 x 2 - 1 x 2
				retVal += (dp((width - 2), isEmpty, isEmpty));
			}

			else if (((topIsempty == true) && (bottomIsempty == false)) ||
				((topIsempty == false) && (bottomIsempty == true)))
			{

				// ▣
				// ▣
				// 1 x 1

				// ▣
				// ▣▣
				// 1 x 2

				// 1 x 1
				retVal += (dp((width - 1), isEmpty, isEmpty));
				// 1 x 2
				retVal += (dp((width - 1), isEmpty, isfilled));
			}


			//둘다 찬 경우
			else
			{
				// ▣
				// ▣
				// 1 x 1
				retVal += (dp((width - 1), isEmpty, isEmpty));
			}
			retVal = retVal % 1000000007;
			wallMemoization[width][topIndex][bottomIndex] = retVal;
		}

		return retVal;
	}

	void printWallMemoization()
	{
		std::cout << "\n";
		for (int i = 0; i < this->wallWidth; i++)
		{
			std::cout << wallMemoization[i][0][0] << " " << wallMemoization[i][0][1] << " " << wallMemoization[i][1][0] << " " << wallMemoization[i][1][1] << "\n";
		}
	}
};


int main()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	std::string inputStr;
	std::getline(std::cin, inputStr);
	std::stringstream ss(inputStr);

	CTile* cTile = new CTile();

	int32_t tempVal;
	ss >> tempVal;
	cTile->setWallWidth(tempVal);
	cTile->printNumberOfCases();
	//cTile->printWallMemoization();
	delete cTile;
}

 

입력

100

결과

315583898

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---