방 바닥의 길이와 너비를 나타내는 두 개의 숫자 n과 m이 주어집니다. 목표는 1Xm 크기의 타일을 사용하여 이 바닥을 타일로 만들 수 있는 방법의 수를 계산하는 것입니다.
예를 들어
입력
n=3 m=2
출력
Count the number of ways to tile the floor of size n x m using 1 x m size tiles are: 3
설명
방법은 아래와 같이 배열된 3개의 1x2 타일입니다 -
입력
n=3 m=3
출력
Count the number of ways to tile the floor of size n x m using 1 x m size tiles are: 2
설명
The ways will be three 1x3 tiles arranged vertically and horizontally. Only two ways.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
이 접근 방식에서 우리는 n의 값을 확인합니다. n이 m보다 작고 값이 1이면 1Xm 크기의 바닥 전체에 하나의 타일만 배치됩니다.
n이 m과 같으면 n 1xm 타일을 모두 수직으로, 모두 수평으로 배치하는 2가지 방법이 있습니다. n이 m보다 크면 이전 방법을 사용하여 방법을 계산합니다 - way[n−1]+ways[m−1].
-
바닥과 타일의 크기에 대해 정수 m과 n을 사용합니다.
-
way_tile_floor(int N, int M) 함수는 1 x m 크기의 타일을 사용하여 n x m 크기의 바닥을 타일링하는 방법의 수를 반환합니다.
-
인덱스 i=N의 현재 값에 대한 타일 수를 저장하려면 길이가 N+1인 배열 arr[ ]를 사용합니다.
-
arr[0]의 경우 타일은 0입니다. 따라서 arr[0]=0입니다.
-
i=1에서 i=N까지 for 루프를 사용하여 rr[]을 트래버스합니다. 각 arr[i]에 대해 i>M이면 이전 값을 사용하여 개수를 계산합니다. arr[i]=arr[i − 1] + arr[i − M].
-
i=1 및 또는 i
-
i=M인 경우 arr[i]=2로 설정합니다.
-
for 루프의 끝에서 arr[N]은 타일을 정렬하는 방법의 수를 갖습니다.
-
결과로 ar[N]을 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int ways_tile_floor(int N, int M){
int arr[N + 1];
arr[0] = 0;
for (int i = 1; i <= N; i++){
if (i > M){
arr[i] = arr[i − 1] + arr[i − M];
}
else if (i < M || i == 1){
arr[i] = 1;
} else {
arr[i] = 2;
}
}
return arr[N];
}
int main(){
int n = 3, m = 2;
cout<<"Count the number of ways to tile the floor of size n x m using 1 x m size tiles are: "<<ways_tile_floor(n, m);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count the number of ways to tile the floor of size n x m using 1 x m size tiles are: 3