๋ฌธ์ ๋งํฌ: programmers.co.kr/learn/courses/30/lessons/43105
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ์ ์ ์ผ๊ฐํ
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30
programmers.co.kr
๋ฌธ์ ์ค๋ช
๊ฑฐ์ณ์จ ์ซ์๋ค์ ํฉ์ ์ต๋๊ฐ์ ์ ์ฅํ๋ dp ํ ์ด๋ธ์ ์์ฑํฉ๋๋ค.
triangle[i][j]์ ๋๋ฌํ๋ ๋ฐฉ๋ฒ์ ๋ ๊ฐ์ง ๋ฐฉ๋ฒ์ด ์์ต๋๋ค.
- triangle[i - 1][j - 1]์์ triangle[i][j]๋ก ๊ฐ๊ธฐ
- triangle[i - 1][j]์์ triangle[i][j]๋ก ๊ฐ๊ธฐ
dp[i][j]๋ ์ ๋ ๊ฐ์ง ๊ฐ ์ค์์ ์ต๋๊ฐ์ ์ ์ฅํฉ๋๋ค.
์๋ฅผ ๋ค์ด triangle ๋ฐฐ์ด์ด ๋ค์๊ณผ ๊ฐ๋ค๋ฉด
7 | ||||
3 | 8 | |||
8 | 1 | 0 | ||
2 | 7 | 4 | 4 | |
4 | 5 | 2 | 6 | 5 |
dp ํ ์ด๋ธ์ ๋ค์๊ณผ ๊ฐ์ด ๊ณ์ฐ๋ฉ๋๋ค.
7 | ||||
10(7 + 3) | 15(7 + 8) | |||
18(10 + 8) | 16(15 + 1) | 15(15 + 0) | ||
20(18 + 2) | 25(18 + 7) | 20(16 + 4) | 19(15 + 4) | |
24(20 + 4) | 30(25 + 5) | 27(25 + 2) | 26(20 + 6) | 24(19 + 5) |
dp ํ ์ด๋ธ ๊ณ์ฐ์ด ๋๋ ํ์ ๋ง์ง๋ง ์ค์ ์์ ์ค์์ ์ต๋๊ฐ์ ๋ฐํํฉ๋๋ค.
์์ค์ฝ๋
def solution(triangle):
# dp ํ
์ด๋ธ ์ด๊ธฐํ
dp = [[0] * len(triangle) for _ in range(len(triangle))]
dp[0][0] = triangle[0][0]
# ๊ฑฐ์ณ๊ฐ ์ซ์์ ์ต๋๊ฐ ๊ตฌํ๊ธฐ
for i in range(0, len(triangle) - 1):
for j in range(len(triangle[i])):
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + triangle[i + 1][j])
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + triangle[i + 1][j + 1])
return max(dp[-1]) # dp ํ
์ด๋ธ์ ๋ง์ง๋ง ์์๋ค ์ค ์ต๋๊ฐ ๋ฐํ
728x90
'Algorithm > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค / Python] ๋๋์ง (0) | 2021.04.06 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค / Python] ๋ฑ๊ตฃ๊ธธ (0) | 2021.04.06 |
[ํ๋ก๊ทธ๋๋จธ์ค / Python] N์ผ๋ก ํํ (0) | 2021.04.06 |
[ํ๋ก๊ทธ๋๋จธ์ค / Python] ์์ (0) | 2021.04.05 |
[ํ๋ก๊ทธ๋๋จธ์ค / Python] ๊ฐ์ฅ ๋จผ ๋ ธ๋ (0) | 2021.04.05 |