[Hackerrank] [Medium] Candies

https://www.hackerrank.com/challenges/candies/problem

Candies | HackerRank

풀이

• 2번 iteration을 사용.
• 오른쪽으로 iteration돌 때는 오름차순일 때 dp 값을 채워줌.
• 왼쪽으로 iteration돌 때는 내림차순일 때 dp값을 채워줌.

def candies(n, arr):
    n = len(arr)
    # 최소값은 1로 문제에서 주어짐.
    dp = [1] * n
    for i in range(1, n):
        # 다음 원소가 더 크면 dp값을 증가해줌.
        if arr[i-1] < arr[i]:
            dp[i] += dp[i-1]

    # 왼쪽으로 거꾸로 iteration
    for i in range(n-2, -1, -1):
        # 왼쪽 원소가 더 큰 경우, 그리고 현재 dp값이 작을 때 바로 다음 dp값에 1 더해주는걸로 update.
        if arr[i] > arr[i+1] and dp[i] <= dp[i+1]:
            dp[i] = dp[i+1] + 1

    return sum(dp)