[이코테] 그리디 - 곱하기 혹은 더하기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

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

예를 들어, 02984라는 문자열이 주어진다면, 만들어질 수 있는 가장 큰 수는 순서대로 0+2 * 9 * 8 * 4 = 576 이다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.

입력조건

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

출력조건

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

사고과정

• 연습장에 그려보면서 연산할 두 숫자 중에 0이 하나라도 존재할 때는 더하기, 나머지는 곱하기만 하는 그리디 방식으로 문제를 해결하고자 함. DP 테이블 형식과 비슷하게 문제를 풀이 시도 함. 입력 예시 2가지에 대해는 맞았음.
• 하지만 풀이를 보니 연산할 두 숫자 중에 1이 있다면 더하는 것이 커진다는 반례를 놓침. 결국 문제는 틀린 셈이다.(반례를 항상 찾기 어려운 듯 하다. 항상 극단적인 경우를 생각해보도록 하자!)

풀이

1. 나의 풀이

import sys

s = input()
array = [int(x) for x in s]

for i in range(1, len(array)):
    if array[i-1] <= 1 or array[i] <= 1:  # 두 숫자 중 하나가 1일 때도 더하기가 이득!
        array[i] = (array[i-1] + array[i])
    else:
        array[i] = (array[i-1] * array[i])


print(array[-1])

2. 책의 풀이

import sys

s = input()
res = int(s[0])

for i in range(1, len(s)):
	num = int(s[i])
    if num <= 1 or res <= 1:
    	res += num
    else:
        res *= num
 
 print(res)