주어진 양의 정수 N에서 형성될 수 있는 길이 a, b, c의 선분의 최대 수를 찾는 작업이 주어집니다.
이제 예제를 사용하여 무엇을 해야 하는지 이해합시다 -
입력 - N=8, a=3, b=1, c=2
출력 − 8
설명 − N은 만들 수 있는 최대 세그먼트 수인 b의 8개 세그먼트로 나눌 수 있습니다.
입력 - N=13, a=2, b=7, c=3
출력 − 6
아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.
-
MaxSegment() 함수에서 int 유형의 배열 MaxSeg[N +1]를 선언하고 값 -1로 초기화합니다.
-
세그먼트가 없으므로 0번째 인덱스를 0과 동일하게 넣습니다.
-
i=0에서 i
-
위의 if 문 안에 또 다른 문을 넣어 if(i + a <=N) and putMaxSeg[i + a] =max(MaxSeg[i] + 1, MaxSeg[i + a]);
-
b와 c 모두에 대해 위의 단계를 반복합니다.
-
루프 외부에서 MaxSeg[N]을 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int MaxSegment(int N, int a,int b, int c){
/* It will store the maximum number of segments each index can have*/
int MaxSeg[N + 1];
// initialization
memset(MaxSeg, -1, sizeof(MaxSeg));
// 0th index will have 0 segments
MaxSeg[0] = 0;
// traversing for every segments till n
for (int i = 0; i < N; i++){
if (MaxSeg[i] != -1){
if(i + a <= N ){
MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]);
}
if(i + b <= N ){
MaxSeg[i + b] = max(MaxSeg[i] + 1, MaxSeg[i + b]);
}
if(i + c <= N ){
MaxSeg[i + c] = max(MaxSeg[i] + 1, MaxSeg[i + c]);
}
}
}
return MaxSeg[N];
}
int main(){
int N = 13, a = 2, b = 7, c = 3;
cout << MaxSegment(N, a, b, c);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -
6