Python으로 세 개의 숫자를 0으로 만드는 최적의 방법

세 개의 숫자가 있다고 가정해 봅시다. 이때 과제는 이 숫자들을 모두 '0'으로 만들기 위해 필요한 최적의 단계 수를 구하는 것입니다.

예시

입력:

a = 4
b = 4
c = 6

출력:

7

설명

모든 숫자를 '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'씩 제거하는 전략을 사용해야 합니다. 최소 단계 수를 구하기 위해 다음과 같은 로직을 적용할 수 있습니다.

• 세 개의 숫자를 입력받습니다.
• sort 함수를 사용하여 숫자를 오름차순으로 정렬합니다.
• 두 숫자의 합이 나머지 한 숫자보다 작다면, 그 합을 결과로 반환합니다.
• 매 단계마다 두 숫자에서 각각 '1'씩 제거되므로, 모든 숫자를 '0'으로 만드는 데 필요한 단계 수는 (n1 + n2 + n3) / 2가 됩니다.

구현 예제

def maxScore(a: int, b: int, c: int):
    a, b, c = sorted((a, b, c))
    if a + b < c: return a + b
    return (a + b + c)//2
a=4
b=4
c=6
print(maxScore(a,b,c))

위 코드를 실행하면 아래와 같은 결과가 출력됩니다.

실행 결과

7

주어진 입력값 a=4, b=4, c=6에 대해 모든 숫자를 '0'으로 만드는 데 일곱 번의 단계가 필요합니다. 따라서 프로그램은 7을 출력으로 반환합니다.