[알고리즘] 곱하기 혹은 더하기

관련 영상

영상 제목 : (이코테 2021 강의 몰아보기) 2. 그리디 & 구현
https://youtu.be/2zjoKjt97vQ

문제 설명

입력 : 여러 개의 숫자들을 한줄로 입력 ex) 02984
출력 : 사이사이에 + 혹은 * 를 넣어서 만들 수 있는 가장 큰 수를 출력
주의할 점 : 무조건 순서대로 연산이 행해진다. 즉, * 가 + 보다 먼저 수행된다는 규칙을 무시한다.

문제 풀이

앞에서부터 단계별로 조지면서 해당 단계에서 덧셈과 곱셉중에 뭐가 더 높은 숫자를 만들지만 생각한다. 그렇게 계속 앞으로 나간다.

정당성 분석

덧셈과 곱셈은 자연수끼리의 연산일 때 0이 아닌 이상 작아지지 않는다. 따라서 무조건 단계 단계에서 높은 수를 찾아나가면 답이다.

내 코드

import sys

numStr = sys.stdin.readline()

numArr = []


for i in range(len(numStr)-1):
    numArr.append(int(numStr[i]))

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

print(numArr[len(numArr)-1])

더 배울점

계산하는 두 수가 0 혹은 1일 때만 더하기가 더 크다.