C++로 계단 색칠하기: 노란색이 연속으로 나오지 않게 칠하는 방법의 수 구하기

이 문제에서는 n개의 계단과 빨간색, 노란색 두 가지 색이 주어집니다. 우리가 해야 할 일은 계단을 색칠하는 모든 방법 중에서 노란색 계단이 연속해서 나오지 않는 경우의 수를 세는 것입니다.

예시를 통해 문제를 자세히 살펴보겠습니다.

입력 예시

출력 결과

설명

계단을 색칠할 수 있는 방법은 YRY, RYR, YRR, RRY, RRR로 총 5가지입니다. 여기서 R은 빨간색(Red), Y는 노란색(Yellow)을 의미합니다.

이제 계단을 색칠하는 방법의 수가 어떤 패턴을 보이는지 단계별로 확인해 보겠습니다.

N = 1일 때, 방법의 수 = 2 : R, Y
N = 2일 때, 방법의 수 = 3 : RY, YR, RR
N = 3일 때, 방법의 수 = 5 : RYR, YRY, RRY, YRR, RRR
N = 4일 때, 방법의 수 = 8 : YRYR, RYRY, RYRR, YRRY, YRRR, RRYR, RRRR, RRRY

위 결과를 살펴보면 흥미로운 규칙을 발견할 수 있습니다. 각 단계의 방법의 수가 바로 앞 두 단계의 합과 같습니다. 즉, 이 문제는 첫 번째 항이 2, 두 번째 항이 3으로 시작하는 피보나치 수열과 동일한 패턴을 따릅니다.

그 이유를 논리적으로 설명하면 다음과 같습니다. n번째 계단을 빨간색으로 칠하면 그 앞의 (n-1)개 계단은 어떤 조합이든 가능하고, n번째 계단을 노란색으로 칠하려면 (n-1)번째 계단은 반드시 빨간색이어야 하므로 (n-2)개 계단의 모든 조합이 가능합니다. 따라서 ways(n) = ways(n-1) + ways(n-2)라는 점화식이 성립하게 됩니다.

이 로직을 구현한 프로그램을 살펴보겠습니다.

예제 코드

#include <iostream>
using namespace std;
int colorSteps(int n) {
    int first = 2;
    int next = 3;
    for (int i = 3; i <= n; i++) {
        next = first + next;
        first = next - first;
    }
    return next;
}
int main(){
    int n = 6;
    cout<<"Number of ways to color "<<n<<" steps is "<<colorSteps(n);
    return 0;
}

실행 결과

Number of ways to color 6 steps is 21

코드 설명

colorSteps 함수는 피보나치 수열의 원리를 활용하여 반복문만으로 답을 계산합니다. 변수 first와 next에 초기값 2와 3을 저장한 뒤, 3번째 계단부터 n번째 계단까지 순회하면서 두 값을 더해 나갑니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

n = 6인 경우, 수열은 2, 3, 5, 8, 13, 21로 진행되므로 최종적으로 21이라는 결과가 출력됩니다.