[그리디 Greedy] 02. 곱하기 혹은 더하기

그리디 (Greedy)

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

 

---

곱하기 혹은 더하기

난이도 ★☆☆  풀이시간 30분  시간제한 1초

 

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하여 숫자 사이에 '×' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 ×를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 ((((0 + 2) × 9) × 8) × 4) = 576입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

 

입력 조건

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

 

출력 조건

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

 

입력 예시1

02984

 

출력 예시1

576

 

입력 예시2

567

 

출력 예시2

210

 

---

코드

# 입력받은 문자열(숫자로만 이루어짐)
strings = input()
# 연산결과 (답) : 첫 번째 문자를 숫자로 변경하여 초기화
result = int(strings[0])

for i in range(1, len(strings)):
    # 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 더하기 수행
    num = int(strings[i])
    if num <= 1 or result <= 1:
        result += num
    # 2 이상부터는 곱하기 수행
    else:
        result *= num

print(result)

---

해설

두 수에 대하여 연산을 수행할 때, 대부분은 '+' 보다는 '×'가 더 값을 크게 만든다.

예를 들어, 7과 9가 있다고 해보자.

이때 더하기를 수행하면 7 + 9 = 16이 되고, 곱하기를 수행하면 7 × 9 = 63이 된다.

 

하지만 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, '×' 보다는 '+'가 더 값을 크게 만든다.

예를 들어, 0과 2가 있다고 해보자.

이때 더하기를 수행하면 0 + 2 = 2가 되고, 곱하기를 수행하면 0 × 2 = 0이 된다.

또한, 1과 2가 있다고 해보자.

이때 더하기를 수행하면 1 + 2 = 3이 되고, 곱하기를 수행하면 1 × 2 = 2가 된다.

 

따라서 두 수 중에서 하나라도 1 이하인 경우에는 더하고 두 수가 모두 2 이상인 경우에는 곱하면 된다.

 

---

출처

나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년