Algorithm & DataStructure
[코드업 3506] 블럭 채우기 1 (small)
GeonWoo Kim
2020. 5. 10. 17:19
위의 그림처럼 2*n 그리드에에 2 * 1 크기의 블럭을 채울 수 있는 방법의 수를 구하는 문제이다. 처음에는 그리드에 대한 배열을 생성해서 브루트포스 방식으로 모든 방법을 탐색하려고 했다. 차분히 더 생각을 해보니 그런 배열은 필요가 없고 블럭을 세로로 배치하는 경우에는 1만큼 이동하고, 가로로 배치하는 경우에는 2만큼 이동했다고 생각하면 간단한 재귀함수로 풀이가 가능하다. 아래는 아이디어를 구현한 결과물이다.
#include <iostream>
using namespace std;
int answer = 0;
void fillGrid(int idx, int len) {
// 기저사례: 범위를 넘었다면 종료
if (idx > len) return;
// 기저사례: 끝까지 채웠다면 종료
if (idx == len) {
answer++;
return;
}
// 세로로 둔다.
fillGrid(idx + 1, len);
// 가로로 둔다.
fillGrid(idx + 2, len);
}
int main() {
int len;
cin >> len;
fillGrid(0, len);
cout << answer << endl;
return 0;
}
이 문제를 기록하는 이유는 항상 문제를 읽고 문제에서 설명한 그대로를 코드에 옮기는 습관이 있었기 때문이다. '가로를 2, 새로를 1'로 배치하는 아이디어같이 더 좋은 방법을 문제에서 생각하는 연습을 해야한다.