728x90
반응형
# 초기 코드 ( 틀림 )
# 계단을 3번 연속 밟을 수 없다.
# 마지막은 꼭 밟아야 한다.
# 한번에 하나나 두개의 계단을 오른다.
n = int(input()) # 계단의 개 수 1<= n <= 300
data = [0]
for i in range(1,n+1):
data.append(int(input()))
result = [0]*301
if n == 1 :
print ( data[1])
elif n == 2 :
print ( data[1]+data[2])
else :
result[1] = data[1]
result[2] = data[1]+data[2]
k = 1
for i in range(3,n-1):
# 전에 연속으로 2번 밟은 경우
a = data[i-2]+data[i-1]
# 전에 연속으로 2번 안 밝은 경우
b = max (data[i-2]+data[i], data[i-1]+data[i])
result[i] = max (a,b) + result[i-3]
if i == n-2 :
if a> b:
# 만약 마지막 전전 계단을 밟았다면, 1 안 밟았다면 0
k = 0
# 만약 마지막 전전꺼를 밟
if ( k == 0 ):
print( result[n-2]+ data[n-1]+ data[n])
else :
print( result[n-2]+ data[n])
# 정답
n = int(input()) # 계단의 개 수 1<= n <= 300
data = [0 for i in range(301)]
for i in range(n):
data[i] = int(input())
result = [0 for i in range(301)]
result[0] = data[0]
result[1] = data[0]+ data[1]
result[2] = max ( data[1] , data[0]) + data[2]
# 경우의 수
# 전 계단 안 밟는게 가장 큰 경우
# 전전 계단 안 밟는게 가장 큰 경우
for i in range(3, n):
result[i] = max ( result[i-3] + data[i-1]+ data[i], result[i-2]+data[i])
print ( result[n-1] )
# 조금 더 간단하게
n = int(input())
data = [0]
for i in range(n): data.append(int(input()))
dp = [0, data[1]]
if n >= 2 : dp.append(data[1]+data[2])
for i in range( 3, n+1):
dp.append( max( dp[i-3]+data[i-1]+data[i], dp[i-2]+data[i] ))
print(dp[n])
728x90
반응형
'백준 > 다이나믹 프로그래밍' 카테고리의 다른 글
# 2193 이친수 (0) | 2020.09.11 |
---|---|
# 1932 정수 삼각형 (0) | 2020.09.11 |
# 1149 RGB 거리 (0) | 2020.09.11 |
# 11726 2xn 타일링 (0) | 2020.09.11 |
# 1003 피보나치 함수 (0) | 2020.09.11 |