C++로 길이 a, b, c 선분의 최대 개수 구하는 방법

이 문제는 양의 정수 N이 주어졌을 때, 이를 길이가 각각 a, b, c인 선분들로 나누었을 때 만들 수 있는 선분의 최대 개수를 구하는 것입니다.

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

예시 1

입력: N = 8, a = 3, b = 1, c = 2

출력: 8

설명: N = 8을 길이가 1(b)인 선분 8개로 나눌 수 있으며, 이것이 만들 수 있는 최대 선분 개수입니다.

예시 2

입력: N = 13, a = 2, b = 7, c = 3

출력: 6

해결 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• MaxSegment() 함수 안에서 크기가 N + 1인 int형 배열 MaxSeg[]를 선언하고 모든 값을 -1로 초기화합니다. -1은 해당 길이를 만들 수 없음을 의미합니다.
• 0번째 인덱스는 선분이 하나도 없는 상태이므로 MaxSeg[0] = 0으로 설정합니다.
• i = 0부터 i < N까지 반복하면서 MaxSeg[i] != -1인지 확인합니다. 즉, 현재 위치에 도달 가능한 경우만 처리합니다.
• 도달 가능한 위치라면, i + a <= N, i + b <= N, i + c <= N 조건을 각각 검사한 뒤 다음과 같이 값을 갱신합니다.
  MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]);
• b와 c에 대해서도 동일한 과정을 반복합니다.
• 루프가 끝나면 MaxSeg[N]을 반환합니다. 이 값이 길이 N을 만들 수 있는 최대 선분 개수입니다. 만약 -1이라면 어떤 조합으로도 정확히 N을 만들 수 없다는 뜻입니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

int MaxSegment(int N, int a, int b, int c){
    /* 각 인덱스(길이)별로 만들 수 있는 최대 선분 개수를 저장 */
    int MaxSeg[N + 1];
    // 초기화
    memset(MaxSeg, -1, sizeof(MaxSeg));
    // 0번 인덱스는 선분이 0개인 상태
    MaxSeg[0] = 0;
    // 0부터 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

N = 13일 때, 길이 2(a)인 선분 5개와 길이 3(c)인 선분 1개를 조합하면 총 6개의 선분으로 나눌 수 있으며, 이것이 가능한 최대 개수입니다.