๐Ÿ’ป Algorithm/Python

[Python] ๋ฐฑ์ค€ - 2579 ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ (DP)

์„ ์ฃผ 2021. 10. 26. 13:08

๐Ÿ‘† ์ฒซ ๋ฒˆ์งธ ์‹œ๋„ (์ธ๋ฑ์Šค ์—๋Ÿฌ)

- dp ํ…Œ์ด๋ธ” ๋งŒ๋“ค์–ด์„œ d[1], d[2]๊ฐ’์„ ๋ฏธ๋ฆฌ ์ง€์ •ํ•ด์ฃผ๋Š” ๊ฒฝ์šฐ๋Š” ์ž…๋ ฅ๊ฐ’ n์ด 1, 2์ผ ์ƒํ™ฉ๋„ ์ƒ๊ฐํ•ด์•ผ ํ•œ๋‹ค.

- ๋ฐฑ์ค€์—์„œ ๋Ÿฐํƒ€์ž„ ์—๋Ÿฌ(IndexError) ๋‚˜๋ฉด ๋ฌธ์ œ ์กฐ๊ฑด์—์„œ ์ž…๋ ฅ๊ฐ’ ๋ฒ”์œ„ ํ™•์ธํ•˜๊ธฐ

n = int(input())
steps = [int(input()) for _ in range(n)]

d = [0] * n
d[0] = steps[0]
d[1] = steps[0] + steps[1]
d[2] = steps[2] + max(steps[0], steps[1])
for i in range(3, n):
    d[i] = steps[i] + max(d[i-2], d[i-3] + steps[i-1])
print(d[n-1])

 

โœŒ ๋‘ ๋ฒˆ์งธ ์‹œ๋„ (์„ฑ๊ณต)

- ๋‚ฎ์€ ๊ณ„๋‹จ๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ ์œ„๋กœ ์˜ฌ๋ผ๊ฐ€๋„ ๋˜์ง€๋งŒ, ๊ฐ€์žฅ ์œ„์— ์žˆ๋Š” ๋งˆ์ง€๋ง‰ ๊ณ„๋‹จ์„ ๊ผญ ๋ฐŸ์•„์•ผ ํ•œ๋‹ค๋Š” ์กฐ๊ฑด์ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๋งˆ์ง€๋ง‰ ๊ณ„๋‹จ์—์„œ๋ถ€ํ„ฐ ์ถœ๋ฐœํ•˜๋Š” ๊ฒƒ์œผ๋กœ ์ƒ๊ฐํ•˜๋ฉด ํ’€๊ธฐ ์ˆ˜์›”ํ•˜๋‹ค.

 

- ๋งˆ์ง€๋ง‰ ๊ณ„๋‹จ i์— ์˜ฌ๋ผ์„œ์„œ ๋ดค์„ ๋•Œ, ์ด ๊ณ„๋‹จ์— ๋„๋‹ฌํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ๋‘ ๊ฐ€์ง€์ด๋‹ค.

  โ‘  i-2๋ฒˆ์งธ ๊ณ„๋‹จ์„ ๋ฐŸ์€ ํ›„ i๋ฒˆ์งธ ๊ณ„๋‹จ์— ๋„๋‹ฌ

  โ‘ก i-1๋ฒˆ์งธ ๊ณ„๋‹จ์„ ๋ฐŸ์€ ํ›„ i๋ฒˆ์งธ ๊ณ„๋‹จ์— ๋„๋‹ฌ

  max(d[i-2], d[i-1])

 

- ๊ทธ๋Ÿฌ๋‚˜ ํ›„์ž์˜ ๊ฒฝ์šฐ, ์—ฐ์†๋œ 3๊ฐœ์˜ ๊ณ„๋‹จ์„ ๋ฐŸ์•„์™”์„ ํ™•๋ฅ ์ด ์กด์žฌํ•˜๋ฏ€๋กœ ์ด ํ™•๋ฅ ์„ ๋ฐฐ์ œํ•ด์•ผ ํ•œ๋‹ค.

  ⇒ max(d[i-2], d[i-3]+steps[i-1])

 

- ์ฃผ์–ด์ง„ ์ž…๋ ฅ๊ฐ’ ์กฐ๊ฑด์ด ์ž์—ฐ์ˆ˜์ด๋ฏ€๋กœ n์ด ๊ฐ๊ฐ 1, 2์ผ ๊ฒฝ์šฐ๋ฅผ if๋ฌธ์œผ๋กœ ๋ถ„๊ธฐ์ฒ˜๋ฆฌํ–ˆ๋‹ค.

n = int(input())
steps = [int(input()) for _ in range(n)]

if n == 1:
    print(steps[0])
elif n == 2:
    print(steps[0]+steps[1])
else:
    d = [0] * n
    d[0] = steps[0]
    d[1] = steps[0] + steps[1]
    d[2] = steps[2] + max(steps[0], steps[1])
    for i in range(3, n):
        d[i] = steps[i] + max(d[i-2], d[i-3] + steps[i-1])
    print(d[n-1])

 


๋ฌธ์ œ

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

<๊ทธ๋ฆผ 1>

์˜ˆ๋ฅผ ๋“ค์–ด <๊ทธ๋ฆผ 2>์™€ ๊ฐ™์ด ์‹œ์ž‘์ ์—์„œ๋ถ€ํ„ฐ ์ฒซ ๋ฒˆ์งธ, ๋‘ ๋ฒˆ์งธ, ๋„ค ๋ฒˆ์งธ, ์—ฌ์„ฏ ๋ฒˆ์งธ ๊ณ„๋‹จ์„ ๋ฐŸ์•„ ๋„์ฐฉ์ ์— ๋„๋‹ฌํ•˜๋ฉด ์ด ์ ์ˆ˜๋Š” 10 + 20 + 25 + 20 = 75์ ์ด ๋œ๋‹ค.

<๊ทธ๋ฆผ 2>

๊ณ„๋‹จ ์˜ค๋ฅด๋Š” ๋ฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทœ์น™์ด ์žˆ๋‹ค.

  1. ๊ณ„๋‹จ์€ ํ•œ ๋ฒˆ์— ํ•œ ๊ณ„๋‹จ์”ฉ ๋˜๋Š” ๋‘ ๊ณ„๋‹จ์”ฉ ์˜ค๋ฅผ ์ˆ˜ ์žˆ๋‹ค. ์ฆ‰, ํ•œ ๊ณ„๋‹จ์„ ๋ฐŸ์œผ๋ฉด์„œ ์ด์–ด์„œ ๋‹ค์Œ ๊ณ„๋‹จ์ด๋‚˜, ๋‹ค์Œ ๋‹ค์Œ ๊ณ„๋‹จ์œผ๋กœ ์˜ค๋ฅผ ์ˆ˜ ์žˆ๋‹ค.
  2. ์—ฐ์†๋œ ์„ธ ๊ฐœ์˜ ๊ณ„๋‹จ์„ ๋ชจ๋‘ ๋ฐŸ์•„์„œ๋Š” ์•ˆ ๋œ๋‹ค. ๋‹จ, ์‹œ์ž‘์ ์€ ๊ณ„๋‹จ์— ํฌํ•จ๋˜์ง€ ์•Š๋Š”๋‹ค.
  3. ๋งˆ์ง€๋ง‰ ๋„์ฐฉ ๊ณ„๋‹จ์€ ๋ฐ˜๋“œ์‹œ ๋ฐŸ์•„์•ผ ํ•œ๋‹ค.

๋”ฐ๋ผ์„œ ์ฒซ ๋ฒˆ์งธ ๊ณ„๋‹จ์„ ๋ฐŸ๊ณ  ์ด์–ด ๋‘ ๋ฒˆ์งธ ๊ณ„๋‹จ์ด๋‚˜, ์„ธ ๋ฒˆ์งธ ๊ณ„๋‹จ์œผ๋กœ ์˜ค๋ฅผ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ, ์ฒซ ๋ฒˆ์งธ ๊ณ„๋‹จ์„ ๋ฐŸ๊ณ  ์ด์–ด ๋„ค ๋ฒˆ์งธ ๊ณ„๋‹จ์œผ๋กœ ์˜ฌ๋ผ๊ฐ€๊ฑฐ๋‚˜, ์ฒซ ๋ฒˆ์งธ, ๋‘ ๋ฒˆ์งธ, ์„ธ ๋ฒˆ์งธ ๊ณ„๋‹จ์„ ์—ฐ์†ํ•ด์„œ ๋ชจ๋‘ ๋ฐŸ์„ ์ˆ˜๋Š” ์—†๋‹ค.

๊ฐ ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ ์ˆ˜๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ ์ด ๊ฒŒ์ž„์—์„œ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ด ์ ์ˆ˜์˜ ์ตœ๋Œ“๊ฐ’์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์— ๊ณ„๋‹จ์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ œ์ผ ์•„๋ž˜์— ๋†“์ธ ๊ณ„๋‹จ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ๊ฐ ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ณ„๋‹จ์˜ ๊ฐœ์ˆ˜๋Š” 300์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๊ณ , ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ ์ˆ˜๋Š” 10,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ๊ฒŒ์ž„์—์„œ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ด ์ ์ˆ˜์˜ ์ตœ๋Œ“๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

6

10

20

15

25

10

20

์˜ˆ์ œ ์ถœ๋ ฅ 1

75