ํฐ์คํ ๋ฆฌ ๋ทฐ
ํ๋ก๊ทธ๋๋จธ์ค: ๋๋์ง
dirmathfl 2020. 10. 24. 21:31๋ฌธ์
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ๋๋์ง
๋๋์ด ์ด๋ ๋ง์์ ํธ ๊ณํ์ ํ๊ณ ์์ต๋๋ค. ์ด ๋ง์์ ๋ชจ๋ ์ง๋ค์ ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๋๊ทธ๋๊ฒ ๋ฐฐ์น๋์ด ์์ต๋๋ค. ๊ฐ ์ง๋ค์ ์๋ก ์ธ์ ํ ์ง๋ค๊ณผ ๋ฐฉ๋ฒ์ฅ์น๊ฐ ์ฐ๊ฒฐ๋์ด ์๊ธฐ ๋๋ฌธ์ ์ธ์ ํ
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]))
'๐จโ๐ป ์ฝ๋ฉํ ์คํธ > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ๋ก๊ทธ๋๋จธ์ค: ๋ฐฉ๋ฌธ ๊ธธ์ด (0) | 2020.10.25 |
---|---|
ํ๋ก๊ทธ๋๋จธ์ค: ์ ๊ตญ์ฌ์ฌ (0) | 2020.10.25 |
ํ๋ก๊ทธ๋๋จธ์ค: ์กฐ์ด์คํฑ (0) | 2020.10.23 |
ํ๋ก๊ทธ๋๋จธ์ค: ํฐ ์ ๋ง๋ค๊ธฐ (0) | 2020.10.23 |
ํ๋ก๊ทธ๋๋จธ์ค: SQL - IS NULL (0) | 2020.10.21 |