입력으로 양수 N이 주어집니다. 목표는 N을 1, 3, 4의 합으로만 표현할 수 있는 방법의 수를 찾는 것입니다. 예를 들어 N이 4이면 1+1+1+1, 3+1, 1+3, 4로 나타낼 수 있으므로 방법의 수는 4가 됩니다.
예를 들어 이해합시다.
예
입력 - N=5
출력 - N을 1, 3, 4의 합으로 표현하는 다양한 방법은 다음과 같습니다. 6
설명 - 5는 다음과 같이 나타낼 수 있습니다.
- 1+1+1+1+1
- 1+3+1
- 3+1+1
- 1+1+3
- 4+1
- 1+4
입력 - N=6
출력 - N을 1, 3, 4의 합으로 표현하는 다양한 방법은 다음과 같습니다. 9
설명 - 9는 다음과 같이 나타낼 수 있습니다.
- 1+1+1+1+1+1
- 3+1+1+1
- 1+3+1+1
- 1+1+3+1
- 1+1+1+3
- 3+3
- 4+1+1
- 1+4+1
- 1+1+4
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서 우리는 동적 프로그래밍 접근 방식을 사용하여 N을 1, 3 및 4의 합으로 나타낼 수 있는 방법의 수를 계산할 것입니다. 여기서 i는 숫자를 나타내고 arr[i]는 이를 나타내는 방법으로 배열 arr[i]를 사용합니다. 합계로.
기본 사례는
arr[0]=0 ( 안 돼요 )
arr[1]=1 ( 편도 , 1 )
arr[2]=1 (편도, 1+1)
arr[3]=2 ( 1+1+1, 3 )
이제 다른 숫자 4, 5 ... i 등은 arr[i-1]+arr[i-3]+arr[i-4]와 같은 방법을 갖습니다.
- 양수 N을 입력으로 사용합니다.
- Express_sum(int N) 함수는 N을 받아 1, 3, 4의 합으로 N을 표현하는 다양한 방법의 개수를 반환합니다.
- 배열을 사용하여 방법의 개수를 저장합니다.
- 기본 경우 arr[0] =1, arr[1] =1, arr[2] =1 및 arr[3] =2를 초기화합니다.
- i=4에서 i<=N까지의 나머지 값을 탐색합니다.
- 요약 arr[i]는 arr[i - 1] + arr[i - 3] + arr[i - 4]의 합계입니다.
- for 루프가 끝나면 결과로 arr[N]을 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int Expres_sum(int N) {
int arr[N + 1];
arr[0] = 1;
arr[1] = 1;
arr[2] = 1;
arr[3] = 2;
for (int i = 4; i <= N; i++) {
arr[i] = arr[i - 1] + arr[i - 3] + arr[i - 4];
}
return arr[N];
}
int main() {
int N = 5;
cout << "Count of different ways to express N as the sum of 1, 3 and 4 are: " << Expres_sum(N);
return 0;
} 위의 코드를 실행하면 다음 출력이 생성됩니다 -
출력
Count of different ways to express N as the sum of 1, 3 and 4 are: 6