[프로그래머스][메모이제이션] 풍선 터트리기

풍선 터트리기

프로그래머스

 

• 풀이
  • 어떤 수 A를 기준으로 생각했을때,
    • A의 왼편에서 가장 작은 값, A 오른편에서 가장 작은값이 최종적으로 남을 수 있음
  • A는 작은 값을 이길 수 있는 기회가 단 1번 있음
    • = 즉, 작은 값이 2개 이상이면 절대 최종적으로 남겨질 수 없다.
    • 한 쪽에 아무것도 없는 인덱스 0, n-1은 무조건 가능
  • 계속 min,max하면 시간초과
    • 누적합 dp처럼 양 옆에서 해당 위치까지 가장 작은 값을 메모이제이션

def solution(a):
    answer = 0
    n=len(a)
    left=a[:]
    for i in range(1,n):
        left[i]=min(left[i-1],a[i])
    right=a[:]
    for i in range(n-2,-1,-1):
        right[i]=min(right[i+1],a[i])
    
    for idx,cur in enumerate(a):
        if idx==0 or idx==n-1:
            answer+=1 #양끝은 무조건 남을 수 있음
            continue
        if left[idx-1]<cur and right[idx+1]<cur:
            continue
        answer+=1
        
    return answer