์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ/BOJ_Python

[BOJ/Step15] 2579 : ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ (Python)

NaNaRin๐Ÿ™ƒ 2021. 2. 25. 20:46

www.acmicpc.net/problem/2579

 

2579๋ฒˆ: ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ

๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ๊ฒŒ์ž„์€ ๊ณ„๋‹จ ์•„๋ž˜ ์‹œ์ž‘์ ๋ถ€ํ„ฐ ๊ณ„๋‹จ ๊ผญ๋Œ€๊ธฐ์— ์œ„์น˜ํ•œ ๋„์ฐฉ์ ๊นŒ์ง€ ๊ฐ€๋Š” ๊ฒŒ์ž„์ด๋‹ค. <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ™์ด ๊ฐ๊ฐ์˜ ๊ณ„๋‹จ์—๋Š” ์ผ์ •ํ•œ ์ ์ˆ˜๊ฐ€ ์“ฐ์—ฌ ์žˆ๋Š”๋ฐ ๊ณ„๋‹จ์„ ๋ฐŸ์œผ๋ฉด ๊ทธ ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ 

www.acmicpc.net


์•ž์— ๋ฌธ์ œ๋“ค์ด๋ž‘ ๋น„์Šทํ–ˆ๋Š”๋ฐ ์ด๊ฑด ์กฐ๊ธˆ ํ—ค๋งธ๋‹ค..

๋‹ค๋ฅธ ์‚ฌ๋žŒ๋“ค์ด๋ž‘ ๊ฐ™์€ ๋กœ์ง์˜ ์ฝ”๋“œ์ธ๋ฐ ๊ณ„์† ์ธ๋ฑ์Šค ์—๋Ÿฌ๊ฐ€ ๋‚˜์„œ ๋Œ€์ฒด ์™œ๊ทธ๋Ÿฌ๋‚˜ ํ–ˆ๋Š”๋ฐ

stair๋ž‘ cost๋ฅผ n๊นŒ์ง€๋งŒ ์ €์žฅํ•ด์„œ ๊ทธ๋žฌ๋‹ค
n์ด 1์ธ ๊ฒฝ์šฐ๋ž‘ 2์ธ ๊ฒฝ์šฐ์— ๋ฆฌ์ŠคํŠธ ์ธ๋ฑ์Šค ๋„ˆ๋จธ๋กœ ์ ‘๊ทผํ•˜๋‹ˆ๊นŒ ๊ณ„์† ์˜ค๋ฅ˜๊ฐ€ ๋‚œ ๊ฒƒ ใ…œ

์ด๋ฒˆ์—๋„ ๋ฉ์ฒญํ–ˆ๋‹ค...

 

1. ๊ฐ ๊ณ„๋‹จ์˜ ์ ์ˆ˜๋ฅผ stair ๋ฆฌ์ŠคํŠธ์— ์ €์žฅํ•˜๊ณ  ๊ฐ ๊ณ„๋‹จ์— ๋„๋‹ฌํ•  ์ ์ˆ˜์˜ ์ตœ๋Œ“๊ฐ’์„ ์ €์žฅํ•  cost๋ฆฌ์ŠคํŠธ๋ฅผ ์ƒ์„ฑ, 0์œผ๋กœ ์ดˆ๊ธฐํ™”

2. cost[0]์— stair[0]์„ ์ €์žฅ ( ์ฒซ๋ฒˆ์งธ ๊ณ„๋‹จ์€ ์ด์ „ ๊ณ„๋‹จ์ด ์—†๊ธฐ ๋•Œ๋ฌธ์— ์–ด๋–ป๊ฒŒ ์˜ฌ๋ผ๊ฐ€๋„ ์ ์ˆ˜๊ฐ€ ๊ทธ๋Œ€๋กœ )

3. stair๊ณผ cost๋ฅผ n ํฌ๊ธฐ๋งŒํผ๋งŒ ๋งŒ๋“ค์—ˆ๊ธฐ ๋•Œ๋ฌธ์— n์ด 1๋ณด๋‹ค ํฐ์ง€ ํ™•์ธํ•˜์—ฌ cost[1]์— stair[0] + stair[1]์„ ์ €์žฅ

    => n์ด 1์ด๋ฉด ๊ณ„๋‹จ์ด ํ•˜๋‚˜์ด๊ธฐ ๋•Œ๋ฌธ์— stair[0]๊นŒ์ง€๋ฐ–์— ์ ์ˆ˜๊ฐ€ ์ €์žฅ๋˜์–ด์žˆ์ง€ ์•Š๋‹ค

4. n์ด 2๋ณด๋‹ค ํฐ์ง€ ํ™•์ธํ•˜์—ฌ cost[2]์— stair[2] + (stair[0], stair[1] ์ค‘ ๋” ํฐ ๊ฐ’)์„ ์ €์žฅ

    => stair[2]์— ๊ฐ€๋Š” ๋ฐฉ๋ฒ•์€ stair[0]์„ ๋ฐŸ๊ณ  ๋„˜์–ด๊ฐ€๋Š” ๋ฐฉ๋ฒ•๊ณผ, stair[1]์„ ๋ฐŸ๊ณ  ๋„˜์–ด๊ฐ€๋Š” ๋ฐฉ๋ฒ• ๋‘๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค

5. for๋ฌธ์œผ๋กœ cost[3]๋ถ€ํ„ฐ cost[n-1]๊นŒ์ง€ ์ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•œ๋‹ค

  5-1. cost[n] ์— ๊ฐ€๋Š” ๋ฐฉ๋ฒ•์€ ๋‘๊ฐ€์ง€์ด๋‹ค

  5-2. stair[n-1] + stair[n-3] ์„ ๋ฐŸ๋Š” ๋ฐฉ๋ฒ•.

          => ์„ธ ๊ณ„๋‹จ์„ ์—ฐ์†์œผ๋กœ ๋ฐŸ์•„์„œ๋Š” ์•ˆ๋˜๊ธฐ ๋•Œ๋ฌธ์— ๋ฐ”๋กœ ์ „ ๊ณ„๋‹จ์„ ๋ฐŸ์•˜๋‹ค๋ฉด ๋ฌด์กฐ๊ฑด ๊ทธ ์ „์ „ ๊ณ„๋‹จ์„ ๋ฐŸ์•„์•ผ๋งŒ ํ•œ๋‹ค

  5-3.  stair[n-2] ์„ ๋ฐŸ๋Š” ๋ฐฉ๋ฒ•. ๋‘ ์นธ ์ „์˜ ๊ณ„๋‹จ์„ ๋ฐŸ์„ ์ˆ˜ ์žˆ๋‹ค.

  => ์„ธ ์นธ ์ „์˜ ๊ณ„๋‹จ๊นŒ์ง€ ์˜ค๋Š” ์ตœ์ข… ์ ์ˆ˜ + ํ•œ ์นธ ์ „์˜ ๊ณ„๋‹จ ๋‹จ๋… ์ ์ˆ˜ ์™€ ๋‘์นธ ์ „์˜ ๊ณ„๋‹จ๊นŒ์ง€ ์˜ค๋Š” ์ตœ์ข… ์ ์ˆ˜๋ฅผ ๋น„๊ตํ•˜์—ฌ ๋” ํฐ ๊ฐ’์„ stair[n]์— ๋”ํ•ด์ค€๋‹ค

  => stair[i] + max(stair[i-1] + cost[i-3], cost[i-2])

 

# 2579.py

n = int(input())

stair = [int(input()) for _ in range(n)]
cost = [0 for _ in range(n)]

cost[0] = stair[0]

if n > 1:
    cost[1] = stair[1] + stair[0]
if n > 2:
    cost[2] = stair[2] + max(stair[0], stair[1])

for i in range(3, n):
    cost[i] = stair[i] + max(stair[i-1] + cost[i-3], cost[i-2])

print(cost[n-1])