[Greedy] 이코테 “곱하기 혹은 더하기” Python 풀이

문제

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

입력 조건

• 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1 <= S의 길이 <= 20)

출력 조건

• 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.

입력 예시

02984

576

출력 예시

576

210

풀이

• 일반적으로 특정한 두 수에 대하여 연산을 수행할 때, ‘+’ 보다는 ‘x’가 값을 더 크게 만든다.
• 하지만, 두 수 중에서 하나라도 ‘0’ 혹은 ‘1’인 경우엔, 곱하기보다 더하기를 수행하는 것이 더 효율적이다.
  • 1 x 2 = 2, 1 + 2 = 3
• 따라서, 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1 이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱하면 된다.
• 추가적으로, 첫 번째 정수를 초기 결과값으로 적용하는 방식을 사용할 수 있다.

예제 코드

import sys

# 입력 문자열
s = list(map(int, list(sys.stdin.readline().rstrip())))

# 첫 번째 정수를 초기 결과값으로 지정
result = s[0]

# 두 번째 정수부터 탐색 시작
for i in range(1, len(s)):
    # 해당 정수가 1 이하이거나, 초기 결과값이 1 이하일 경우
    if (s[i] <= 1 or result <= 1):
        # 결과값에 해당 수를 더한다.
        result += s[i]
    # 해당 정수가 2 이상일 경우
    else:
        # 현재 결과값에 해당 수를 곱한다.
        result *= s[i]

print(result)

참고

• 이것이 취업을 위한 코딩 테스트다. with python