도로변 구역에 건물 짓기: 가능한 모든 경우의 수 계산하기

문제 정의

도로변에 n개의 구역이 주어져 있으며, 각 구역은 도로를 기준으로 양쪽 두 면에 건물을 지을 수 있습니다. 단, 두 집 사이에는 최소 한 칸의 빈 공간이 있어야 한다는 조건이 붙습니다. 이때 이 부지 전체에 건물을 배치할 수 있는 경우의 수는 총 몇 가지일까요?

하나의 구역을 기준으로 보면 건물을 짓는 방식은 다음 네 가지로 나눌 수 있습니다.

도로의 한쪽 면에만 건설
도로의 반대쪽 면에만 건설
아무 건물도 짓지 않음
도로 양쪽 면 모두에 건설

입력 및 출력

프로그램은 건물을 지을 구역의 개수 n을 입력으로 받습니다. 예를 들어 구역 수가 3일 때 프로그램은 다음과 같이 총 25가지 방법을 출력합니다.

Enter Number of sections: 3
Buildings can be constructed in 25 different ways.

알고리즘 설계

핵심 아이디어는 도로의 한쪽 면에 대한 경우의 수를 먼저 구한 뒤, 양쪽 면이 서로 독립적이므로 그 값을 제곱하는 것입니다.

도로 한쪽 면에 대해서는 다음 두 가지 상태를 추적합니다.

countEnd: 마지막 구역에 건물이 세워진 배치의 수
countEndSpace: 마지막 구역이 빈 공간인 배치의 수

인접한 두 구역에 동시에 건물을 지을 수 없으므로, 새 구역을 하나씩 추가할 때 다음 점화식이 성립합니다.

새 구역에 건물을 지으려면 바로 앞 구역이 반드시 비어 있어야 하므로 countEnd는 이전의 countEndSpace 값이 됩니다.
새 구역을 비워 두는 것은 앞 구역의 상태와 무관하게 항상 가능하므로 countEndSpace는 이전 countEnd와 countEndSpace의 합이 됩니다.

이 점화식은 피보나치 수열과 동일한 구조입니다. 구역이 하나뿐일 때(n = 1) 한쪽 면에는 '짓는다 / 짓지 않는다'의 2가지가 가능하고, 양쪽 면이 독립적이므로 2 × 2 = 4가지가 됩니다.

constructionWays(n)

입력: 구역의 개수 n
출력: 건물을 지을 수 있는 총 경우의 수

Begin
    if n = 1, then
        return 4
    countEnd := 1
    countEndSpace := 1

    for i := 2 to n, do
        prevCountEnd := countEnd
        prevCountEndSpace := countEndSpace
        countEndSpace := countEnd + prevCountEndSpace
        countEnd := prevCountEndSpace
    done

    answer := countEndSpace + countEnd
    return answer^2
End

C++ 구현 예제

#include<iostream>
using namespace std;

int constructionWays(int n) {
    if (n == 1)          // 구역이 하나뿐인 경우
        return 4;        // 한 구역에서 가능한 4가지 방법을 반환

    // 마지막이 건물인 경우와 빈 공간인 경우의 개수를 초기화
    int countEnd=1, countEndSpace=1, prevCountEnd, prevCountEndSpace;

    for (int i=2; i<=n; i++) {      // 2번째 구역부터 n번째 구역까지 반복
        prevCountEnd = countEnd;
        prevCountEndSpace = countEndSpace;

        countEndSpace = countEnd + prevCountEndSpace;
        countEnd = prevCountEndSpace;
    }

    // 빈 공간으로 끝나는 경우와 건물로 끝나는 경우의 합
    int answer = countEndSpace + countEnd;

    return (answer*answer);         // 도로 양쪽이므로 제곱하여 반환
}

int main() {
    int n;
    cout << "Enter Number of sections: ";
    cin >> n;
    cout << "Buildings can be constructed in " << constructionWays(n) <<" different ways." ;
}

실행 결과

Enter Number of sections: 3
Buildings can be constructed in 25 different ways.

동작 과정 살펴보기 (n = 3)

구역이 3개일 때 알고리즘이 어떻게 25라는 답을 도출하는지 단계별로 확인해 보겠습니다.

초기값: countEnd = 1, countEndSpace = 1 (첫 번째 구역 기준)
i = 2: countEndSpace = 1 + 1 = 2, countEnd = 1 → 한쪽 면의 누적 경우의 수 = 3
i = 3: countEndSpace = 1 + 2 = 3, countEnd = 2 → 한쪽 면의 누적 경우의 수 = 5

따라서 한쪽 면당 5가지이고, 양쪽 면이 서로 독립적이므로 5 × 5 = 25가지가 최종 답이 됩니다.