python | 곱하기 혹은 더하기 | 그리디(greedy)

대표적인 그리디 문제 중 또 쉬운 난이도인 곱하기 혹은 더하기 문제를 풀어보겠다.

 

 

📒 문제

---

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '*' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.

단, +보다 X를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 ((((0+2) 9) 8) * 4) = 576 입니다.

 

입력 예시1:
02984

출력 예시1:
576

 

입력 예시2:
567

출력 예시2:
210

 

🤸‍♀️ 문제 분석

---

 

숫자를 하나씩 확인하며,

💡연산하는 숫자가 0 혹은 1일 때는 더하는 것이 곱하기보다 더 큰 수를 만들 수 있다. (그 외는 곱하기가 더 큰 수다.)

 

이를 가능하게 하기 위해서는

💡 출력값의 초기값은 입력값의 첫번째 숫자로 할당한다 

 

🧮코드

---

numbers = input()

# 결과값은 숫자의 첫번째값으로 초기화한다.
result = int(numbers[0])

# 숫자를 하나씩 확인
for n in numbers[1:]:
    # 문자를 숫자형으로 바꿔준다
    n = int(n)
    
    # 두 값 중 하나가 0이나 1이면 더하는 것이 크다
    if result == 0 or result == 1 or n == 0 or n == 1:
        # print(f'{result+n} = {result} + {n}')
        result += n
    
    # 그 외는 곱하는 것이 크다
    else:
        # print(f'{result*n} = {result} * {n}')
        result *= n
    
print(result)