인프런 커뮤니티 질문&답변

1. 현재 학습 진도

• 몇 챕터/몇 강을 수강 중이신가요?

1-9 알고리즘 더 풀어보기 (1)

2. 어려움을 겪는 부분

문제의 조건이 모든 연산은 왼쪽에서 순서대로 이루어진다. 라고 되어있어, 연산을 해야하는 순간에 가장 최대가 될 수 있는 연산만 골라서 계산한다 라고 떠올려보았습니다.

그렇다면 해당 문제를 greedy로 생각해봐도 괜찮을까요?

아직 진도 초반이지만, 평소 코테 문제를 볼 때 어느 부분에 힌트를 잡고 어떤 알고리즘으로 풀어야하는지에 대해 감이 없는 상태라서 이런 문제들(연산이 순서대로 된다던지, 거스름돈 문제처럼 단위가 결정된다던지)은 greedy로 보면 되는지 여쭙고싶습니다.

아래는 풀이한 코드입니다.

def find_max_plus_or_multiply(array):
    answer = array[0]
    for n in range(1,len(array)):
        if answer + array[n] > answer * array[n]:
            answer += array[n]
        else:
            answer *= array[n]
    return answer


result = find_max_plus_or_multiply
print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))