b_계단 오르기_2579

문제

한번에 1,2 jump 가능
연속된 3개 불가
마지막껀 반드시밟아야
애를밟앗을때가장높은점수
애를안밟았을때 가장 높은점수
약간 다이나믹프로그래믹

풀이 1

dfs로 모두 모두 다 탐색하는 일종의 브루드포스로 풀어보았다.
당연히 시간초과가 났다

import sys

n = int(sys.stdin.readline().strip())
stair = []
for i in range(n):
    stair.append(int(sys.stdin.readline().strip()))

result = 0

def dfs(i,visited,value):
    global result
    # print(i,visited,value,result)
    canVisit = True
    if i>=n:
        if bool(visited[i-1]):
            # print("비교!")
            result=max(result,value)
        return
    if i>1:
        canVisit = not (bool(visited[i-1] & visited[i-2]))
    if canVisit:
        visited[i]=1
        dfs(i+1,visited,value+stair[i])
        visited[i]=0
    dfs(i+1,visited,value)

init_visit = [0]*n
dfs(0,init_visit,0)
print(result)

풀이2

다이나믹 프로그래밍방식으로 풀었다.

0-안밟음,1-밟음

밟을 수 있는 경우의 수
101
110
011
010
100, 001, 000 은 당연히 101,010 보다 클 수 없으므로 제외햇다.
그다음의 경우의 수
101 - 이전 110 or 010
110 - 이전 011
011 - 이전 101
010 - 이전 101

import sys

n = int(sys.stdin.readline().strip())
stair = []
for i in range(n):
    stair.append(int(sys.stdin.readline().strip()))

def get_point(i,arr):
    # print(i,arr)
    global stair
    global n
    if i >= n-2:
        return max(arr[i-1][0],arr[i-1][2])
    # i는 -2한거임
    arr[i][0]= max(arr[i-1][1]+stair[i+2],arr[i-1][3]+stair[i+2])
    arr[i][1]= arr[i-1][2]
    arr[i][2]= arr[i-1][0]+stair[i+2]
    arr[i][3]= arr[i-1][0]
    return get_point(i+1,arr)
    

def solution():
    global n
    global stair
    if n<3:
        return sum(stair)
    arr = [[0]*4 for _ in range(n-2)]
    arr[0][0]= stair[0]+stair[2]
    arr[0][1]= stair[0]+stair[1]
    arr[0][2]= stair[1]+stair[2]
    arr[0][3]= stair[1]
    return get_point(1,arr)

print(solution())

풀이3

다른 풀이
https://bio-info.tistory.com/158

점화식으로 풀엇다 나처럼 경우의 수를 직접지정하지않고
항상 마지막 stair을 밟는다고 정하고 점화식을 설계하였다