C++에서 인접한 두 개의 색상이 노란색이 아닌 두 가지 색상으로 계단을 페인트하는 방법

n개의 계단과 이 계단을 칠할 2가지 색상(빨간색과 노란색)이 제공됩니다. 우리의 임무는 연속되는 두 계단이 노란색으로 표시되지 않도록 계단을 페인트할 수 있는 방법의 수를 세는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

3

출력

5

설명

The ways in which stairs can be painted are YRY, RYR, YRR, RRY, RRR. here R denotes red color, Y denotes yellow color.

이 문제를 해결하기 위해 계단을 칠할 수 있는 방법의 수를 봅시다.

N =1, way(1) =2 :R, Y

N =2, way(2) =3 :RY, YR, RR

N =3, way(3) =5 :RYR, YRY, RRY, YRR, RRR

N =4, way(4) =8 :YRYR, RYRY, RYRR, YRRY, YRRR, RRYR, RRRR, RRRY.

따라서 이러한 경우로부터 2를 첫 번째 요소로, 3을 두 번째 요소로 시작하는 피보나치 수열을 유도할 수 있습니다.

우리 논리의 작동을 설명하는 프로그램,

예시

#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