codeup 4564

# 4564 계단 오르기

# 룰1 : 계단은 1칸이나 2칸 올라갈 수 있음
# 룰2 : 계단 1칸을 연속 3번 올라갈 수 없음
# 룰3 : 마지막 계단은 무조건 밟아야 함.
import sys

sys.setrecursionlimit(1000)

N = int(input())

score_array = [0]
inserted_score = [int(input()) for _ in range(N)]

for n in inserted_score:
    score_array.append(n)

score_array.append(0)
score_array.append(0)

gain_array = []

# tempPath = []
# params
# 남은 계단수,  획득한 점수, 제약페널티
def climb(remain, scored, penalty):

    if remain == 0:
        gain_array.append(scored)
        # tempPath.append(path)
        return
    elif remain < 0:
        return
    else:

        # 현재 위치
        pos = N - remain

        # 획득할 점수
        # score_array[pos + 올라갈 높이]
        # if penalty == 2:
        #     # print('출력되면 안됨.')
        #     climb(remain - 2, score_array[pos + 2] + scored, 0, path+'2')

        if penalty == 1:
            climb(remain - 2, score_array[pos + 2] + scored, 0)

        else:
            climb(remain - 2, score_array[pos + 2]+ scored, 0)
            climb(remain - 1, score_array[pos + 1]+ scored, penalty + 1)


climb(N, 0, -1) #시작점은 페널티를 -1로 만들어야 하는게 중요.
gain_array.sort(reverse=True)
print(gain_array[0])


사실 이문제는 시간초과, 메모리 초과로 실패했다.
메모이제이션을 사용하는 방법으로 로직을 다시 설계해야 하고,
룰의 패턴을 로직에 녹여야 풀 수 있는 문제다.