๊ธ€ ์ž‘์„ฑ์ž: ํƒ์‹œ ์šด์ „์‚ฌ
๋ฐ˜์‘ํ˜•

๐Ÿ‘จโ€๐Ÿซ ์ •์ˆ˜ ์‚ผ๊ฐํ˜• ๋ฌธ์ œ ํ’€์–ด๋ณด๊ธฐ


๐Ÿ˜ƒ ๋‚˜์˜ ์ฝ”๋“œ

def solution(tri):
    m_lst = []
    for row in tri:
        lst = []
        if len(m_lst) == 0:
            lst.append(row[0]);
        else:   
            for idx, num in enumerate(row):
                if idx == 0:
                    lst.append(m_lst[-1][idx] + num)
                elif idx == len(row)-1:
                    lst.append(m_lst[-1][-1] + num)
                else:
                    lst.append(max(m_lst[-1][idx-1],m_lst[-1][idx]) + num)
        m_lst.append(lst)
    return max(m_lst[-1])

DP(Dynamic Programming, ๋™์ ๊ณ„ํš๋ฒ•)์„ ์ด์šฉํ•ด ํ•ด๊ฒฐํ•œ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. DP์˜ ๊ณ„ํš์— ๋”ฐ๋ผ ์ „์ฒด ๋ฌธ์ œ๋ฅผ ์ž‘์€ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด์„œ ํ’€๊ฒ ์Šต๋‹ˆ๋‹ค. ์ฃผ์–ด์ง„ ์‚ผ๊ฐํ˜•์ด ์•„๋‹Œ ๊ทธ๋ณด๋‹ค ์ž‘์€ ์‚ผ๊ฐํ˜•์— ๋Œ€ํ•œ ๋ฌธ์ œ๋ฅผ ํ’€์–ด์„œ ๊ทธ ํฌ๊ธฐ๋ฅผ ์ ์  ํ‚ค์›Œ์„œ ์ฃผ์–ด์ง„ ์‚ผ๊ฐํ˜•๊นŒ์ง€ ๋‚˜์•„๊ฐ‘๋‹ˆ๋‹ค.

m_lst๋ผ๋Š” ์ƒˆ๋กœ์šด ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด ์ด ๊ณณ์—๋Š” ์•„๋ž˜๋กœ ๊ฑฐ์ณ๊ฐ„ ์ˆซ์ž์˜ ํ•ฉ์ด ๊ฐ€์žฅ ํฐ ๊ฒฝ์šฐ์˜ ๊ฒฐ๊ณผ๊ฐ’๋งŒ ์ €์žฅํ•˜๋„๋ก ์ฝ”๋“œ๋ฅผ ์งญ๋‹ˆ๋‹ค. ๋‹ค์Œ์œผ๋กœ DP์˜ ๋‹ค์Œ ํŠน์ง•์ธ ๋‹ค๋ฅธ ์‹œํ–‰์˜ ๊ฒฐ๊ณผ๊ฐ’์„ ์‚ฌ์šฉํ•˜์—ฌ ์ž‘์€ ์‚ผ๊ฐํ˜•์—์„œ์˜ ํŠน์ • ์œ„์น˜์˜ ํ•ฉ์˜ ์ตœ๋Œ€๊ฐ’์„ ์ด์šฉํ•˜์—ฌ ๋‹ค์Œ ์ตœ๋Œ€๊ฐ’์„ ๊ตฌํ•ฉ๋‹ˆ๋‹ค. ์ด๋Ÿฐ ์‹์œผ๋กœ ๋งˆ์ง€๋ง‰๊นŒ์ง€ ๊ตฌํ•œ ๋’ค max(m_lst[-1])์„ ์ด์šฉํ•˜์—ฌ ์‚ผ๊ฐํ˜•์˜ ๋งจ ์•„๋ž˜์นธ์˜ ์ตœ๋Œ€๊ฐ’ ๋ฐฐ์—ด์ค‘ ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•˜๋ฉด ๋ฌธ์ œ๊ฐ€ ๋งˆ๋ฌด๋ฆฌ๋ฉ๋‹ˆ๋‹ค.

Written with StackEdit.


๋ฐ˜์‘ํ˜•