#백준 2579번 #파이썬 #알고리즘 #문이과통합중

### 문제설명 

 

아래와 같이 계단인 척 하는 리스트가 있다.

stair = [10,20,15,25,10,20]

n번쨰 계단은 stair[n]을 의미한다. 

n = 0 부터 차례대로 계단을 고르는데, 고른 계단의 누적합이 최대가 되도록 고른다. 

 

### 제약조건 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

 

 

### 예제입력 

6 10 20 15 25 10 20

 

### 예제출력

75

 

### 문제풀이 1 

전형적인 다이나믹 프로그래밍 종류의 문제. 통칭 DP(Dynamic Programming) 유형. 해당 종류의 문제를 많이 접해보지 못해서 index 를 활용해서 돌아가는 방식으로 접근하였다. 최대값의 index 를 리스트에 넣고 나중에 합계를 다시 계산해서 리턴하는 방식으로. 예제에 대한 맞는 출력을 리턴하는데는 성공을 하였으나.. 아쉽게도 연속된 세자리 숫자에 대한 처리를 고민하다가 그냥 gg쳤다. 

# Sample Test 
tmp = [10, 20, 15, 25, 10, 20 ]

n = 0
blank = [] 
while True:
  
  #max(tmp[n+1], tmp[n+2])
  if tmp[n+1] == max(tmp[n+1], tmp[n+2]):
    max_idx = n+1
  elif tmp[n+2] == max(tmp[n+1], tmp[n+2]):
    max_idx = n+2

  n = max_idx
  blank.append(n) 
  print(max_idx)

  #max_idx가 len(tmp)에 도착하는 두가지 예외처리 
  if n == (len(tmp)-1):
    break
  elif n == (len(tmp)-2):
    blank.append(n+1)
    break

print(blank)

ele_sum = 0
for k in blank:
  ele_sum += tmp[k]

print(ele_sum + tmp[0])

### 문제풀이2

해당문제에 대한 정석적인 해답. 

개인적으로 생각하는 키워드는.. 누적합의 수열. 

n = int(input())
s = [0 for i in range(301)]
dp = [0 for i in range(301)]

for i in range(n):
    s[i] = int(input())

# 고정
dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[1] + s[2], s[0] + s[2])


# 유동
for i in range(3, n):
    dp[i] = max(dp[i - 3] + s[i - 1] + s[i], 
                dp[i - 2] +            s[i])

print(s[:n])
print(dp[:n])

print(dp[n - 1])