[Medium] NumberSolitaire

[문제]

0 ~ N-1 의 배열에서 1~6 칸씩 이동하여 N-1에 도착할 때까지 방문한 index의 값의 합 중 가장 큰 값을 찾는 문제

NumberSolitaire coding task - Learn to Code - Codility

[코드]

시간복잡도 : O(N)

맨 끝에서 부터 1-6칸씩 이동하며 N-1에 도착할 때까지 방문한 index의 값의 합 중 최대값을 기록하고 0번째 배열의 계산 값을 반환

def solution(A):
    # write your code in Python 3.6
    maxSum = [-1000000001 for i in range(len(A))]
    maxSum[len(A)-1] = A[-1]

    for i in range(len(A)-2, -1, -1) :
        for j in range(1, 7) :
            if i+j < len(A) :
                maxSum[i] = max(maxSum[i], A[i] + maxSum[i+j])
            else :
                break

    return maxSum[0]