[코드업 3506] 블럭 채우기 1 (small)

 

 

위의 그림처럼 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'로 배치하는 아이디어같이 더 좋은 방법을 문제에서 생각하는 연습을 해야한다.