```
백준 2718번 4 X N 타일 채우기 C++ 구현해보기
```
이번 글을 통해 배워갈 내용
- 백준 2718번 풀이
- 간단한 클래스 및 배열 연습
https://www.acmicpc.net/problem/2718
2718번: 타일 채우기
첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 타일의 너비 N이다. N은 자연수
www.acmicpc.net
백준 2718번 타일채우기는
난이도 골드 등급의 문제로서
4 x N 크기의 타일을
2 x 1 혹은 1 x 2 타일로 채우는 경우의 수를 테스트 케이스 만큼 구하는 문제이다.
N의 범위는 결과값이 int의 최대값미만인 경우까지이다.
30분 정도 위에 링크를 방문하셔서 풀어보시고
안풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.
한줄씩 한줄씩 타일을 채워나가면서
DP 방식을 사용하였습니다.
문제의 정답은 int범위지만
공간 복잡도는 큰 문제가 아닌것 같아서
longlong으로 진행했고
중간값을 저장하는 배열을 만들고
각 경우에 수에 따라 하나씩 작업을 하였습니다.
물론 수학적 접근으로 코드를 줄이는 것도 가능하지만
경우의 수를 최대한 적어서 다른 분들이 읽는데
지장이 없도록
가독성이나 이해도를 생각하면서 작성하다 보니
코드가 길어진것 같습니다.
먼저 메인 함수를 보시면
테스트 케이스를 입력 받고
입력받은 테스트 케이스 값에 따라서
반복해서
타일 너비를 설정하고
DP를 계산해줍니다.
시간 초과떄문에
각 테스트 케이스에서 저장한 DP값을 재사용 하였습니다.
int main()
{
std::cin.tie(NULL);
std::ios::sync_with_stdio(false);
std::string inputStr;
int32_t testCase;
std::cin >> testCase;
std::cin.ignore();
CTile* cTile = new CTile();
for (int i = 0; i < testCase; i++)
{
std::getline(std::cin, inputStr);
std::stringstream ss(inputStr);
int32_t tempVal;
ss >> tempVal;
cTile->setWallWidth(tempVal);
cTile->printNumberOfCases();
//cTile->printWallMemoization();
}
delete cTile;
}
DP 값을 받아서 출력하기 위해 너비값을 사용하였으며(wallWidth)
너비가 0이면 0을 출력합니다.
void printNumberOfCases()
{
long long retVal = 0;
if(wallWidth != 0)
{
retVal = dp(wallWidth, true, true, true, true);
}
std::cout << retVal << "\n";
}
row는 각 행을 나타내며 true면 비어있는것, false면 차있는 것입니다.
비어있는 공간에만 입력 가능하며
각 케이스 별로 간단한 그림과 설명을 넣었습니다.
long long dp(int32_t width, bool row1Isempty, bool row2Isempty, bool row3Isempty, bool row4Isempty)
{
long long retVal = 0;
const int32_t row1Index = row1Isempty ? 1 : 0;
const int32_t row2Index = row2Isempty ? 1 : 0;
const int32_t row3Index = row3Isempty ? 1 : 0;
const int32_t row4Index = row4Isempty ? 1 : 0;
const bool isfilled = false;
const bool isEmpty = true;
// 남은 길이 1 이하
if (width <= 1)
{
if (width == 1)
{
// 위아래 중 하나만 빈 경우
if (((row1Isempty == true) && (row2Isempty == false) && (row3Isempty == false) && (row4Isempty == false)) ||
((row1Isempty == false) && (row2Isempty == true) && (row3Isempty == false) && (row4Isempty == false)) ||
((row1Isempty == false) && (row2Isempty == false) && (row3Isempty == true) && (row4Isempty == false)) ||
((row1Isempty == false) && (row2Isempty == false) && (row3Isempty == false) && (row4Isempty == true))
)
{
retVal = 0;
}
// 모두 찬 경우
else if ((row1Isempty == false) && (row2Isempty == false) && (row3Isempty == false) && (row4Isempty == false))
{
retVal = 0;
}
// 사이드로 하나씩만 찬 경우
else if ((row1Isempty == true) && (row2Isempty == false) && (row3Isempty == false) && (row4Isempty == true))
{
retVal = 0;
}
// 그 외
else
{
retVal = 1;
}
}
else if (width == 0)
{
// 모두 빈 경우
if ((row1Isempty == true) && (row2Isempty == true) && (row3Isempty == true) && (row4Isempty == true))
{
retVal = 1;
}
else
{
retVal = 0;
}
}
else
{
retVal = 0;
}
}
else if (wallMemoization[width].getArr(row1Index, row2Index, row2Index, row3Index) != -1)
{
retVal = wallMemoization[width].getArr(row1Index, row2Index, row2Index, row3Index);
}
else
{
const int32_t openNum = row1Index + row2Index + row3Index + row4Index;
// 다 열린 경우
if (openNum == 4)
{
// ▣
// ▣
// ▣
// ▣
// 2 x 1 2 x 1
retVal += (dp((width - 1), isEmpty, isEmpty, isEmpty, isEmpty));
// ▣
// ▣
// ▣▣
// ▣▣
// 2 x 1 - 1 x 2 - 1 x 2
retVal += (dp((width - 1), isEmpty, isEmpty, isfilled, isfilled)) * 2;
// ▣▣
// ▣
// ▣
// ▣▣
// 2 x 1 - 1 x 2 - 1 x 2
retVal += (dp((width - 1), isfilled, isEmpty, isEmpty, isfilled));
// ▣▣
// ▣▣
// ▣▣
// ▣▣
// 1 x 2 - 1 x 2 - 1 x 2 - 1 x 2
retVal += (dp((width - 2), isEmpty, isEmpty, isEmpty, isEmpty));
}
// 하나만 닫힌 경우
else if (openNum == 3)
{
// ▣
//
//
//
if ((row1Isempty == false) || (row4Isempty == false))
{
// ▣
// ▣
// ▣▣
// ■
retVal += (dp((width - 1), isEmpty, isfilled, isEmpty, isEmpty));
// ▣▣
// ▣
// ▣
// ■
retVal += (dp((width - 1), isfilled, isEmpty, isEmpty, isEmpty));
// ▣▣
// ▣▣
// ▣▣
// ■
// 1 x 2 - 1 x 2 - 1 x 2
retVal += (dp((width - 1), isfilled, isfilled, isfilled, isEmpty));
}
//
// ▣
//
//
else
{
// ▣▣
// ■
// ▣
// ▣
retVal += (dp((width - 1), isfilled, isEmpty, isEmpty, isEmpty));
// ▣▣
// ■
// ▣▣
// ▣▣
retVal += (dp((width - 1), isfilled, isEmpty, isfilled, isfilled));
}
}
else if (openNum == 2)
{
//
// ▣
// ▣
//
if ((row2Isempty == false) && (row3Isempty == false))
{
// ▣▣
// ▣
// ▣
// ▣▣
retVal += (dp((width - 1), isfilled, isEmpty, isEmpty, isfilled));
}
// ▣
//
//
// ▣
else if ((row1Isempty == false) && (row4Isempty == false))
{
// ▣
// ▣
// ▣
// ▣
retVal += (dp((width - 1), isEmpty, isEmpty, isEmpty, isEmpty));
// ▣
// ▣▣
// ▣▣
// ▣
retVal += (dp((width - 1), isEmpty, isfilled, isfilled, isEmpty));
}
// ▣
// ▣
//
//
else
{
// ▣
// ▣
// ▣
// ▣
retVal += (dp((width - 1), isEmpty, isEmpty, isEmpty, isEmpty));
// ▣
// ▣
// ▣▣
// ▣▣
retVal += (dp((width - 1), isEmpty, isEmpty, isfilled, isfilled));
}
}
// 세개 닫힌 경우
else if (openNum == 1)
{
// ▣
// ▣
// ▣
// ▣▣
retVal += (dp((width - 1), isEmpty, isEmpty, isEmpty, isfilled));
// ▣
// ▣
// ▣▣
// ▣
retVal += (dp((width - 1), isEmpty, isEmpty, isfilled, isEmpty));
}
// 다 닫힌 경우
else
{
// ▣
// ▣
// ▣
// ▣
retVal += (dp((width - 1), isEmpty, isEmpty, isEmpty, isEmpty));
}
//retVal = retVal % 10007;
wallMemoization[width].setArr(row1Index, row2Index, row2Index, row3Index, retVal);
}
return retVal;
}눈치 빠른 분들은 아시겠지만 전체 코드는 방금전 글에서 쓴 코드를 그대로 차용해서 진행 한 것을 알수 있습니다.
전체 코드는 다음과 같습니다
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
class WallCol
{
private:
long long arr[2][2][2][2] = { { { {-1,-1}, { -1,-1 } }, { {-1,-1}, { -1,-1 } } }, { { {-1,-1}, { -1,-1 } }, { {-1,-1}, { -1,-1 } } } };
public:
long long getArr(int32_t index1, int32_t index2, int32_t index3, int32_t index4)
{
return arr[index1][index2][index3][index4];
}
void setArr(const int32_t index1, const int32_t index2, const int32_t index3, const int32_t index4, const long long val)
{
arr[index1][index2][index3][index4] = val;
}
};
class CTile
{
private:
std::array<WallCol, 1000002> wallMemoization;
int32_t wallWidth;
public:
CTile()
{
wallWidth = 0;
}
~CTile()
{
}
void setWallWidth(const int32_t _wallWidth)
{
this->wallWidth = _wallWidth;
}
void printNumberOfCases()
{
long long retVal = 0;
if(wallWidth != 0)
{
retVal = dp(wallWidth, true, true, true, true);
}
std::cout << retVal << "\n";
}
long long dp(int32_t width, bool row1Isempty, bool row2Isempty, bool row3Isempty, bool row4Isempty)
{
long long retVal = 0;
const int32_t row1Index = row1Isempty ? 1 : 0;
const int32_t row2Index = row2Isempty ? 1 : 0;
const int32_t row3Index = row3Isempty ? 1 : 0;
const int32_t row4Index = row4Isempty ? 1 : 0;
const bool isfilled = false;
const bool isEmpty = true;
// 남은 길이 1 이하
if (width <= 1)
{
if (width == 1)
{
// 위아래 중 하나만 빈 경우
if (((row1Isempty == true) && (row2Isempty == false) && (row3Isempty == false) && (row4Isempty == false)) ||
((row1Isempty == false) && (row2Isempty == true) && (row3Isempty == false) && (row4Isempty == false)) ||
((row1Isempty == false) && (row2Isempty == false) && (row3Isempty == true) && (row4Isempty == false)) ||
((row1Isempty == false) && (row2Isempty == false) && (row3Isempty == false) && (row4Isempty == true))
)
{
retVal = 0;
}
// 모두 찬 경우
else if ((row1Isempty == false) && (row2Isempty == false) && (row3Isempty == false) && (row4Isempty == false))
{
retVal = 0;
}
// 사이드로 하나씩만 찬 경우
else if ((row1Isempty == true) && (row2Isempty == false) && (row3Isempty == false) && (row4Isempty == true))
{
retVal = 0;
}
// 그 외
else
{
retVal = 1;
}
}
else if (width == 0)
{
// 모두 빈 경우
if ((row1Isempty == true) && (row2Isempty == true) && (row3Isempty == true) && (row4Isempty == true))
{
retVal = 1;
}
else
{
retVal = 0;
}
}
else
{
retVal = 0;
}
}
else if (wallMemoization[width].getArr(row1Index, row2Index, row2Index, row3Index) != -1)
{
retVal = wallMemoization[width].getArr(row1Index, row2Index, row2Index, row3Index);
}
else
{
const int32_t openNum = row1Index + row2Index + row3Index + row4Index;
// 다 열린 경우
if (openNum == 4)
{
// ▣
// ▣
// ▣
// ▣
// 2 x 1 2 x 1
retVal += (dp((width - 1), isEmpty, isEmpty, isEmpty, isEmpty));
// ▣
// ▣
// ▣▣
// ▣▣
// 2 x 1 - 1 x 2 - 1 x 2
retVal += (dp((width - 1), isEmpty, isEmpty, isfilled, isfilled)) * 2;
// ▣▣
// ▣
// ▣
// ▣▣
// 2 x 1 - 1 x 2 - 1 x 2
retVal += (dp((width - 1), isfilled, isEmpty, isEmpty, isfilled));
// ▣▣
// ▣▣
// ▣▣
// ▣▣
// 1 x 2 - 1 x 2 - 1 x 2 - 1 x 2
retVal += (dp((width - 2), isEmpty, isEmpty, isEmpty, isEmpty));
}
// 하나만 닫힌 경우
else if (openNum == 3)
{
// ▣
//
//
//
if ((row1Isempty == false) || (row4Isempty == false))
{
// ▣
// ▣
// ▣▣
// ■
retVal += (dp((width - 1), isEmpty, isfilled, isEmpty, isEmpty));
// ▣▣
// ▣
// ▣
// ■
retVal += (dp((width - 1), isfilled, isEmpty, isEmpty, isEmpty));
// ▣▣
// ▣▣
// ▣▣
// ■
// 1 x 2 - 1 x 2 - 1 x 2
retVal += (dp((width - 1), isfilled, isfilled, isfilled, isEmpty));
}
//
// ▣
//
//
else
{
// ▣▣
// ■
// ▣
// ▣
retVal += (dp((width - 1), isfilled, isEmpty, isEmpty, isEmpty));
// ▣▣
// ■
// ▣▣
// ▣▣
retVal += (dp((width - 1), isfilled, isEmpty, isfilled, isfilled));
}
}
else if (openNum == 2)
{
//
// ▣
// ▣
//
if ((row2Isempty == false) && (row3Isempty == false))
{
// ▣▣
// ▣
// ▣
// ▣▣
retVal += (dp((width - 1), isfilled, isEmpty, isEmpty, isfilled));
}
// ▣
//
//
// ▣
else if ((row1Isempty == false) && (row4Isempty == false))
{
// ▣
// ▣
// ▣
// ▣
retVal += (dp((width - 1), isEmpty, isEmpty, isEmpty, isEmpty));
// ▣
// ▣▣
// ▣▣
// ▣
retVal += (dp((width - 1), isEmpty, isfilled, isfilled, isEmpty));
}
// ▣
// ▣
//
//
else
{
// ▣
// ▣
// ▣
// ▣
retVal += (dp((width - 1), isEmpty, isEmpty, isEmpty, isEmpty));
// ▣
// ▣
// ▣▣
// ▣▣
retVal += (dp((width - 1), isEmpty, isEmpty, isfilled, isfilled));
}
}
// 세개 닫힌 경우
else if (openNum == 1)
{
// ▣
// ▣
// ▣
// ▣▣
retVal += (dp((width - 1), isEmpty, isEmpty, isEmpty, isfilled));
// ▣
// ▣
// ▣▣
// ▣
retVal += (dp((width - 1), isEmpty, isEmpty, isfilled, isEmpty));
}
// 다 닫힌 경우
else
{
// ▣
// ▣
// ▣
// ▣
retVal += (dp((width - 1), isEmpty, isEmpty, isEmpty, isEmpty));
}
//retVal = retVal % 10007;
wallMemoization[width].setArr(row1Index, row2Index, row2Index, row3Index, retVal);
}
return retVal;
}
void printWallMemoization()
{
wallMemoization[0].setArr(1, 1, 1, 1, 4);
wallMemoization[1].setArr(0, 0, 0, 0, 2);
std::cout << "\n";
for (int i = 0; i < this->wallWidth; i++)
{
for (int index1 = 0; index1 < 2; index1++)
{
for (int index2 = 0; index2 < 2; index2++)
{
for (int index3 = 0; index3 < 2; index3++)
{
for (int index4 = 0; index4 < 2; index4++)
{
std::cout << wallMemoization[i].getArr(index1, index2, index3, index4) << " ";
}
}
}
}
std::cout << "\n";
}
}
};
int main()
{
std::cin.tie(NULL);
std::ios::sync_with_stdio(false);
std::string inputStr;
int32_t testCase;
std::cin >> testCase;
std::cin.ignore();
CTile* cTile = new CTile();
for (int i = 0; i < testCase; i++)
{
std::getline(std::cin, inputStr);
std::stringstream ss(inputStr);
int32_t tempVal;
ss >> tempVal;
cTile->setWallWidth(tempVal);
cTile->printNumberOfCases();
//cTile->printWallMemoization();
}
delete cTile;
}
입력 및 출력
10
1
1
2
5
3
11
4
36
5
95
6
281
20
616891945
25
114079985111
읽어주셔서 감사합니다
무엇인가 얻어가셨기를 바라며
오늘도 즐거운 코딩하시길 바랍니다 ~ :)
참조 및 인용
C++ Primer
Introduction to Algorithms
https://codemasterkimc.tistory.com/35
C++ 이론을 배울수 있는 곳 정리
개요 C++을 배우는 책, 강의, 블로그, 링크 등을 공유합니다. (링크 및 간략한 설명을 하였으나 만약 원작자가 링크를 거는것을 원치 않을 경우 연락주시기 바랍니다.) 서적 https://www.amazon.com/Prime
codemasterkimc.tistory.com
https://codemasterkimc.tistory.com/50
300년차 개발자의 좋은 코드 5계명 (Clean Code)
이번 글을 통해 배워갈 내용 좋은 코드(Clean Code)를 작성하기 위해 개발자로서 생각해볼 5가지 요소를 알아보겠습니다. 개요 좋은 코드란 무엇일까요? 저는 자원이 한정적인 컴퓨터 세상에서 좋
codemasterkimc.tistory.com
728x90
'C++ > C++ 알고리즘' 카테고리의 다른 글
| 백준 20499번 K/D/A 점수변환 C++ 구현해보기 (0) | 2021.09.12 |
|---|---|
| 백준 3107번 IPv6 변환 C++ 구현해보기 (0) | 2021.09.12 |
| 백준 11727번 2xn 타일링2 C++ 구현해보기 (0) | 2021.09.11 |
| 백준 11726번 2xn 타일링 C++ 구현해보기 (0) | 2021.09.11 |
| 백준 14852번 타일채우기3 C++ 구현해보기 (0) | 2021.09.11 |
