C++에서 ax + by + cz = n 조건을 만족하며 x + y + z의 합을 최대화하는 방법

정수 a, b, c, n이 주어졌을 때, 방정식 ax + by + cz = n을 만족하면서 x + y + z의 합이 최대가 되는 경우를 찾는 것이 목표입니다.

공식 유도

방정식을 z에 대해 정리하면 다음과 같습니다.

cz = n − (ax + by)
z = (n − (ax + by)) / c

x와 y의 값을 하나씩 고정한 뒤 위 공식으로 z를 계산하고, 각 조합(x, y, z)마다 합을 구하여 그중 최댓값을 저장하면 됩니다.

입력 및 출력 예시

예시 1

n = 6, a = 3, b = 4, c = 5;

출력:

x + y + z의 최댓값은 2입니다.

설명: x = 2, y = 0, z = 0일 때 ax + by + cz = n을 만족합니다.

3×2 + 0×4 + 0×5 = 6 = n

예시 2

n = 4, a = 3, b = 1, c = 2;

출력:

x + y + z의 최댓값은 4입니다.

설명: x = 0, y = 4, z = 0일 때 ax + by + cz = n을 만족합니다.

0×3 + 4×1 + 0×2 = 4 = n

알고리즘 접근 방법

• 정수 a, b, c, n은 방정식 ax + by + cz = n의 계수와 상수로 사용됩니다.
• 함수 maximize(int n, int a, int b, int c)는 a, b, c, n을 입력받아 조건을 만족하는 x + y + z의 최댓값을 반환합니다.
• 가능한 모든 ax 값에 대해 반복합니다: for(i = 0; i <= n; i += a)
• 가능한 모든 by 값에 대해 반복합니다: for(j = 0; j <= n − i; j += b)
• z = (n − (i + j)) / c를 계산합니다.
• x = i / a, y = j / b를 구한 뒤 x + y + z를 temp에 저장합니다.
• temp가 지금까지의 최댓값 maxx 이상이면 maxx를 갱신합니다.
• 모든 반복이 끝나면 maxx를 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int maximize(int n, int a, int b, int c){
    int maxx = 0;
    // i는 ax의 가능한 값
    for (int i = 0; i <= n; i += a)
        // j는 by의 가능한 값
        for (int j = 0; j <= n - i; j += b) {
            float z = (n - (i + j)) / c;
            // z가 정수인 경우만 유효한 해
            if (floor(z) == ceil(z)) {
                int x = i / a;
                int y = j / b;
                int temp = x + y + z;
                if (temp >= maxx)
                    maxx = temp;
            }
        }
    return maxx;
}
int main(){
    int n = 6, a = 3, b = 4, c = 5;
    cout << "x + y + z의 최댓값 : " << maximize(n, a, b, c);
    return 0;
}

실행 결과

x + y + z의 최댓값 : 2

시간 복잡도

두 개의 중첩 반복문을 사용하므로 시간 복잡도는 약 O(n² / (a·b))입니다. n이 작은 경우에는 충분히 효율적이지만, n이 매우 커질 경우 동적 계획법(DP) 기반 접근을 함께 고려하는 것이 좋습니다.