C++로 세 개의 숫자를 모두 0으로 만드는 최소 단계 구하기

세 개의 숫자가 주어져 있다고 가정해 봅시다. 이때 우리가 해야 할 과제는, 매번 두 개의 숫자에서 1씩 빼는 연산만 허용될 때 모든 숫자를 '0'으로 만들기 위해 필요한 최적의(최소) 단계 수를 구하는 것입니다.

문제 예시

입력:

a = 4
b = 4
c = 6

출력:

설명: 모든 숫자를 0으로 만들기까지의 최적 단계는 다음과 같습니다.

초기 상태: (4, 4, 6)
1번째와 2번째 숫자에서 1씩 제거 → (3, 3, 6)
1번째와 3번째 숫자에서 1씩 제거 → (2, 3, 5)
1번째와 3번째 숫자에서 1씩 제거 → (1, 3, 4)
1번째와 3번째 숫자에서 1씩 제거 → (0, 3, 3)
2번째와 3번째 숫자에서 1씩 제거 → (0, 2, 2)
2번째와 3번째 숫자에서 1씩 제거 → (0, 1, 1)
2번째와 3번째 숫자에서 1씩 제거 → (0, 0, 0)

따라서 모든 숫자를 0으로 만드는 데 필요한 총 단계 수는 7입니다.

문제 해결 접근 방법

이 문제를 효율적으로 해결하려면, 항상 두 숫자의 합이 나머지 하나보다 큰 경우에 해당 두 숫자에서 1씩 제거하는 전략을 사용해야 합니다. 이렇게 하면 세 숫자를 균형 있게 줄여나갈 수 있으며, 결과적으로 최소 단계 수를 얻을 수 있습니다.

구체적인 알고리즘은 다음과 같습니다.

세 개의 숫자 a, b, c를 입력으로 받습니다.
a + b > c 이고 a > 0, b > 0인 동안, a와 b에서 각각 1씩 제거하며 단계 수를 증가시킵니다.
위 반복이 끝나면 남은 값들을 처리합니다. 이 시점에는 한 번의 연산으로 두 숫자를 동시에 줄일 수 없으므로, min(c, a + b)만큼 추가 단계가 필요합니다.
총 단계 수를 반환합니다.

C++ 구현 코드

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

int maxSteps(int a, int b, int c) {
    int res = 0;
    // 두 숫자의 합이 나머지 하나보다 클 때, 해당 두 숫자에서 1씩 제거
    while (a + b > c and a > 0 and b > 0) {
        a--;
        b--;
        res++;
    }
    // 남은 숫자들은 한 번에 하나씩만 처리 가능
    res += min(c, a + b);
    return res;
}

int main() {
    int a = 4;
    int b = 4;
    int c = 6;
    cout << maxSteps(a, b, c) << endl;
    return 0;
}

실행 결과

입력값이 a = 4, b = 4, c = 6일 때, 모든 숫자를 0으로 만드는 데 정확히 7단계가 필요하므로 프로그램은 7을 출력합니다.

이 알고리즘의 시간 복잡도는 O(max(a, b, c))이며, 공간 복잡도는 O(1)로 추가 메모리 없이 해결할 수 있습니다. 핵심 아이디어는 매 단계마다 가장 큰 두 숫자를 우선적으로 감소시켜 세 숫자 간의 편차를 최소화하는 것입니다.