September 22, 2020
BOJ 2579λ² : κ³λ¨ μ€λ₯΄κΈ°
κ³λ¨μ μ€λ₯Ό λ λ°λ κ³λ¨μ μ¨μ Έμλ μμ ν©μ μ΅λκ°μ ꡬνλ λ¬Έμ μ΄λ€. κ³λ¨μ μ€λ₯΄λ λ°©λ²μ λ€μκ³Ό κ°λ€. κ³λ¨μ μμμ μ 첫 λ²μ§Έ κ³λ¨μ΄ μλ μμ λ°λ₯λΆν° μμνλ€. μ¦, 첫 λ²μ§Έ κ³λ¨μ μμμ μ΄ μλλ€.
μμ κ³λ¨μ μλ‘ μκ°ν΄λ³΄μ. λ΄κ° λμ°©μ§μ μΈ μ λμ°©νμ λ μ΄λ»κ² μ λμ°©ν μ μμκΉ?
λ§μ½ ν κ³λ¨ μ¬λΌμ μ¨ κ²½μ°λΌλ©΄ κ·Έ μ§μ κ³λ¨μΈ μ λ°μμ κ²μ΄λ€. μ°μλ 3κ°μ κ³λ¨μ λ°μ μ μμΌλ―λ‘ μ κΈ°μ€μΌλ‘ μ μ κ³λ¨μΈ λ₯Ό λ°κ³ μμ κ²μ΄λ€. μ¦, 15 β 10 β 20
μΌλ‘ λ°κ³ μμ κ²μ΄λ€.
λ κ³λ¨μ μ¬λΌμ μ¨ κ²½μ°λ©΄ κ·Έ μ μ κ³λ¨μΈ λ₯Ό λ°κ³ μμ κ²μ΄λ€. μ¦, 25 β 20
μ λ°κ³ μλ€.
κ³λ¨μ κ°μκ° 2κ° μ΄νμΈ κ²½μ° κ³λ¨μ λͺ¨λ λ°λ κ²½μ°κ° μ΅λκ°μ΄ λλ€. κ³λ¨μ κ°μκ° 3κ°μΌ κ²½μ° 1λ²μ§Έ κ³λ¨κ³Ό 2λ²μ§Έ κ³λ¨ μ€ ν° κ°κ³Ό 3λ²μ§Έ κ³λ¨μ ν©μ λ°ννλ©΄ λλ€.
κ³λ¨μ κ°μκ° 4κ° μ΄μμΈ κ²½μ° μμ κ³Όμ μ λ°λ³΅νλ©΄ λλ€. μ¦, ν κ³λ¨μ μ¬λΌμ¨ κ²½μ°μ λ κ³λ¨μ μ¬λΌμ¨ κ²½μ° μ€ κ°μ₯ ν° μλ₯Ό μ μ₯νλ©΄μ κ³λ¨μ μ€λ₯΄λ©΄ λλ€. μ΄λ₯Ό μ νμμΌλ‘ λνλ΄λ©΄ λ€μκ³Ό κ°λ€.
μμμ μμ λ μΉΈμ μ€λ₯Ό μ μλ 건μ§κ° ν·κ°λ Έμλ€. λ¬Έμ μ λ°λ‘ λͺ μλμ§ μμ κ²μ 보λ κ°λ₯νλ€λ κ²μ μ μ μμλ€. λ¬Έμ μ μ νμ¬νμ λΉ λ₯Έ μκ° λ΄μ νμ νλ μ°μ΅μ΄ νμν κ² κ°λ€.
import sys
def result(stair, n):
if len(stair) < 3:
return sum(stair)
table = [stair[0], max(stair[1], stair[0]+stair[1]), max(stair[0], stair[1])+stair[2]]
for i in range(3, n):
table.append(max(stair[i]+stair[i-1]+table[i-3], stair[i]+table[i-2]))
return table[-1]
n = int(sys.stdin.readline())
stair = []
for _ in range(n):
stair.append(int(sys.stdin.readline()))
print(result(stair, n))