ํ‹ฐ์Šคํ† ๋ฆฌ ๋ทฐ

728x90
๋ฐ˜์‘ํ˜•

๋ฌธ์ œ

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋„๋‘‘์งˆ

๋„๋‘‘์ด ์–ด๋Š ๋งˆ์„์„ ํ„ธ ๊ณ„ํš์„ ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๋งˆ์„์˜ ๋ชจ๋“  ์ง‘๋“ค์€ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ๋™๊ทธ๋ž—๊ฒŒ ๋ฐฐ์น˜๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ์ง‘๋“ค์€ ์„œ๋กœ ์ธ์ ‘ํ•œ ์ง‘๋“ค๊ณผ ๋ฐฉ๋ฒ”์žฅ์น˜๊ฐ€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์ธ์ ‘ํ•œ

programmers.co.kr

 

๋ฌธ์ œ ํ’€์ด

 ์ธ์ ‘ํ•œ ๋‘ ์ง‘์€ ๋ฐฉ๋ฒ”์žฅ์น˜๊ฐ€ ์—ฐ๊ฒฐ๋˜์–ด ํ„ธ ์ˆ˜ ์—†๋‹ค๋Š” ์ œํ•œ ์กฐ๊ฑด์„ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ์ด๋•Œ ์ง‘์„ ํ„ธ์–ด์„œ ๊ฐ€์žฅ ํฐ๋ˆ์„ ํ›”์น  ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ“๊ฐ’์„ ๋ฐ˜ํ™˜ํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.

 

  • ์ง‘ 1๊ฐœ : ํ•ด๋‹น ์ง‘์„ ํ„ฐ๋Š” ๊ฒƒ์ด ์ตœ๋Œ€ ๊ฐ’์ด๋‹ค.
  • ์ง‘ 2๊ฐœ : ๋‘˜ ์ค‘์— money๊ฐ€ ํฐ ๊ฒƒ์„ ํ„ฐ๋Š” ๊ฒƒ์ด ์ตœ๋Œ€ ๊ฐ’์ด๋‹ค.
  • ์ง‘ 3๊ฐœ : i์™€ i - 2 ๋˜๋Š” i - 1 ์ง‘์˜ money ์ค‘ ์ตœ๋Œ€๊ฐ’์ธ ๊ฒฝ์šฐ๋ฅผ ํ„ฐ๋Š” ๊ฒƒ์ด ์ตœ๋Œ€์ด๋‹ค.
  • ์ง‘ 3๊ฐœ ์ธ ๊ฒฝ์šฐ์—์„œ ์•Œ ์ˆ˜ ์žˆ๋“ฏ์ด ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๋‹ค์‹œ 2๊ฐ€์ง€๋กœ ๋‚˜๋‰œ๋‹ค.
    • ์ฒซ ๋ฒˆ์งธ ์ง‘์„ ๋ฌด์กฐ๊ฑด ํ„ฐ๋Š” ๊ฒฝ์šฐ.
      • dp[FIRST][0], dp[FIRST][1] = money[0], moeny[0]๋กœ ์ดˆ๊ธฐํ™” ํ•œ๋‹ค.
    • ๋งˆ์ง€๋ง‰ ์ง‘์„ ๋ฌด์กฐ๊ฑด ํ„ฐ๋Š” ๊ฒฝ์šฐ.
      • dp[LAST][0], dp[LAST][1] = 0, money[1]๋กœ ์ดˆ๊ธฐํ™” ํ•œ๋‹ค.

 ์œ„์™€ ๊ฐ™์€ ๊ฒฝ์šฐ๋ฅผ ํ†ตํ•ด ์ง‘์„ ํ„ธ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€๊ฐ’์€ ์ ํ™”์‹์€ dp[i] = max(dp[i - 1], money[i], dp[i - 2])์„ ์œ ์ถ”ํ•  ์ˆ˜ ์žˆ๋‹ค.

 

์ฝ”๋“œ

FIRST, LAST = 0, 1


def solution(money):
    length = len(money)
    dp = [[0] * length for _ in range(2)]
    dp[FIRST][0], dp[FIRST][1] = money[0], money[0]
    dp[LAST][0], dp[LAST][1] = 0, money[1]

    for i in range(2, length):
        if i < length - 1:
            dp[FIRST][i] = max(dp[FIRST][i - 1], money[i] + dp[FIRST][i - 2])
        dp[LAST][i] = max(dp[LAST][i - 1], money[i] + dp[LAST][i - 2])

    return max(max(dp[FIRST]), max(dp[LAST]))

 

 

728x90
๋ฐ˜์‘ํ˜•
๊ธ€ ๋ณด๊ด€ํ•จ
์ตœ๊ทผ์— ์˜ฌ๋ผ์˜จ ๊ธ€
์ตœ๊ทผ์— ๋‹ฌ๋ฆฐ ๋Œ“๊ธ€