[Python] 그리디 알고리즘을 파헤쳐 보자! (곱하기 혹은 더하기)

문제

• 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 떄, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.
• 예를 들어 02984라는 문자열로 만들 수 있는 가장 큰수는 ((((0 + 2) x 9) x 8) x4) = 567입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

입력

02984

출력

576

정답

import sys

s = sys.stdin.readline().strip()
result = int(s[0])

for num in range(1, len(s)):
    num = int(s[num])

    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)

Tip

가장 큰 수를 만들기 위해서는 N1 + N2 보다는 N1 * N2가 더 높다. 하지만, N1과 N2 중 하나라도 1보다 낮을 시 N1 + N2가 더 크게 나오기 때문에 주의하여 알고리즘을 완성시키면 된다.

if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

N1과 N2 중 1보다 낮은 숫자가 있을 시 더하기를 실행하고 아니면 곱하기를 실행한다.

 

Reference

본 그리디 알고리즘 문제 예제 및 개념은 여기에서 참고합니다.