Q2 곱하기 혹은 더하기

각 자리가 숫자로만 이루어진 문자열 S가 주어졌을 때, 모든 숫자 사이에 x 혹은 +를 넣어 결과적으로 만들 수 있는 가장 큰수를 구해서 리턴하시오. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리 모든 연산을 왼쪽에서부터 순서대로 한다고 가정한다.

 

S의 길이는 1이상 20 이하

만들어질 수 있는 큰 수는 항상 20억 이하

 

 

 

음.. 0이나 1이면 더하고 나머지 수는 곱하면 그리디하게 풀 수 있지 않을까? 

+랑 x를 끼워넣는 모든 경우를 전체탐색하는 발상도 해볼수는 있는데 S길이가 20일 경우 2^20의 경우의 수가 발생한다.

 

두 수를 곱하는 경우랑 더하는 경우를 비교해서 연산을 수행해도 된다

nums = list(map(int,input()))

summary = nums[0]
for i in range(1, len(nums)):
    if summary*nums[i] > summary+nums[i]:
        summary *= nums[i]
    else:
        summary += nums[i]

print(summary)

 

혹은

nums = list(map(int,input()))

summary = nums[0]
for i in range(1, len(nums)):
    if summary<=1 or nums[i]<=1:
        summary += nums[i]
    else:
        summary *= nums[i]

print(summary)