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

+ Recent posts