πŸ“ BOJ - 계단 였λ₯΄κΈ°

문제

BOJ 2579번 : 계단 였λ₯΄κΈ°

μ ‘κ·Ό 방법

climbing-stairs

계단을 였λ₯Ό λ•Œ λ°ŸλŠ” 계단에 μ¨μ ΈμžˆλŠ” 수의 ν•©μ˜ μ΅œλŒ€κ°’μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€. 계단을 였λ₯΄λŠ” 방법은 λ‹€μŒκ³Ό κ°™λ‹€. κ³„λ‹¨μ˜ μ‹œμž‘μ μ€ 첫 번째 계단이 μ•„λ‹Œ μ™„μ „ λ°”λ‹₯λΆ€ν„° μ‹œμž‘ν•œλ‹€. 즉, 첫 번째 계단은 μ‹œμž‘μ μ΄ μ•„λ‹ˆλ‹€.

  • 계단은 ν•œ λ²ˆμ— ν•œ 계단씩 λ˜λŠ” 두 계단씩 였λ₯Ό 수 μžˆλ‹€.
  • μ—°μ†λœ μ„Έ 개의 계단을 λͺ¨λ‘ λ°Ÿμ•„μ„œλŠ” μ•ˆ λœλ‹€. 단, μ‹œμž‘μ μ€ 계단에 ν¬ν•¨λ˜μ§€ μ•ŠλŠ”λ‹€.
  • λ§ˆμ§€λ§‰ 도착 계단은 λ°˜λ“œμ‹œ λ°Ÿμ•„μ•Ό ν•œλ‹€.

μ„€λͺ…

μœ„μ˜ 계단을 예둜 μƒκ°ν•΄λ³΄μž. λ‚΄κ°€ 도착지점인 2020에 λ„μ°©ν–ˆμ„ λ•Œ μ–΄λ–»κ²Œ 2020에 도착할 수 μžˆμ„κΉŒ?

λ§Œμ•½ ν•œ 계단 μ˜¬λΌμ„œ 온 경우라면 κ·Έ 직전 계단인 1010을 λ°Ÿμ•˜μ„ 것이닀. μ—°μ†λœ 3개의 계단을 λ°Ÿμ„ 수 μ—†μœΌλ―€λ‘œ 1010을 κΈ°μ€€μœΌλ‘œ μ „μ „ 계단인 1515λ₯Ό 밟고 왔을 것이닀. 즉, 15 β†’ 10 β†’ 20으둜 밟고 왔을 것이닀.

두 계단을 μ˜¬λΌμ„œ 온 경우면 κ·Έ μ „μ „ 계단인 2525λ₯Ό 밟고 왔을 것이닀. 즉, 25 β†’ 20을 밟고 μ™”λ‹€.

κ²°λ‘ 

κ³„λ‹¨μ˜ κ°œμˆ˜κ°€ 2개 μ΄ν•˜μΈ 경우 계단을 λͺ¨λ‘ λ°ŸλŠ” κ²½μš°κ°€ μ΅œλŒ€κ°’μ΄ λœλ‹€. κ³„λ‹¨μ˜ κ°œμˆ˜κ°€ 3개일 경우 1번째 계단과 2번째 계단 쀑 큰 κ°’κ³Ό 3번째 κ³„λ‹¨μ˜ 합을 λ°˜ν™˜ν•˜λ©΄ λœλ‹€.

κ³„λ‹¨μ˜ κ°œμˆ˜κ°€ 4개 이상인 경우 μ•žμ˜ 과정을 λ°˜λ³΅ν•˜λ©΄ λœλ‹€. 즉, ν•œ 계단을 올라온 κ²½μš°μ™€ 두 계단을 올라온 경우 쀑 κ°€μž₯ 큰 수λ₯Ό μ €μž₯ν•˜λ©΄μ„œ 계단을 였λ₯΄λ©΄ λœλ‹€. 이λ₯Ό μ ν™”μ‹μœΌλ‘œ λ‚˜νƒ€λ‚΄λ©΄ λ‹€μŒκ³Ό κ°™λ‹€.

sum[i]=max(stair[i]+stair[iβˆ’1]+sum[iβˆ’3],stair[i]+sum[iβˆ’2])sum[i] = max(stair[i]+stair[i-1]+sum[i-3], stair[i]+sum[i-2])
  • sum[i]sum[i] : ii번째 κ³„λ‹¨κΉŒμ§€ λ°Ÿμ•˜μ„ λ•Œμ˜ 밟고 μ§€λ‚˜μ˜¨ μˆ«μžλ“€μ˜ ν•©
  • stair[i]stair[i] : ii번쨰 계단에 적힌 수

κ΅ν›ˆ

μ‹œμž‘μ μ—μ„œ 두 칸을 였λ₯Ό 수 μžˆλŠ” 건지가 ν—·κ°ˆλ Έμ—ˆλ‹€. λ¬Έμ œμ— λ”°λ‘œ λͺ…μ‹œλ˜μ§€ μ•Šμ€ 것을 λ³΄λ‹ˆ κ°€λŠ₯ν•˜λ‹€λŠ” 것을 μ•Œ 수 μžˆμ—ˆλ‹€. 문제의 μ œν•œμ‚¬ν•­μ„ λΉ λ₯Έ μ‹œκ°„ 내에 νŒŒμ•…ν•˜λŠ” μ—°μŠ΅μ΄ ν•„μš”ν•œ 것 κ°™λ‹€.

μ†ŒμŠ€ μ½”λ“œ

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))

Written by@μ½”λ”©ν•˜λŠ”νŽ­κ·„
파이썬과 웹에 관심 λ§Žμ€ 컴곡 μ „κ³΅μžπŸ‘©β€πŸ’»

GitHubInstagram