|
์ฝ๋ ์์ฑํ๊ธฐ
def solution(triangle):
for i in range(1, len(triangle)):
for j in range(0, len(triangle[i])):
if j==0 :
triangle[i][j]+=triangle[i-1][j]
elif j==len(triangle[i])-1:
triangle[i][j]+=triangle[i-1][j-1]
else:
triangle[i][j]+=max(triangle[i-1][j], triangle[i-1][j-1])
return max(triangle[-1])
Python
๋ณต์ฌ
|
์ฝ๋ ์ค๋ช
ํ๊ธฐ
1.
๋๋ฒ์งธ ํ๋ถํฐ ์์ํ๋ค.
2.
๋ฐ๋ก ์์ ํ์์ ๋์ฌ ์ ์๋ ์ต๋๋ฅผ ๊ตฌํด์ ํ์ฌ ์ธ๋ฑ์ค ๊ฐ๊ณผ ๋ํด์ค๋ค.
a.
์ฒซ๋ฒ์งธ ์ด์ (i-1, j)์ ๊ฑฐ์ณ ๋ด๋ ค์ค๋ ๋ฐฉ๋ฒ๋ง ์กด์ฌํ๋ค.
b.
๋ง์ง๋ง ์ด์ (i-1, j-1)์ ๊ฑฐ์ณ ๋ด๋ ค์ค๋ ๋ฐฉ๋ฒ๋ง ์กด์ฌํ๋ค.
c.
์ด ์ธ์ ์ธ๋ฑ์ค๋ (i-1, j) ๋๋ (i-1, j-1) ์ค ์ต๋๋ฅผ ๊ฑฐ์ณ ๋ด๋ ค์ฌ ์ ์๋ค.
3.
๋งจ ๋ง์ง๋ง ํ์ ์ต๋๊ฐ์ ๋ฐํํด์ค๋ค.