[프로그래머스] 파이썬 문제풀이 - 정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

첫 풀이

1. 위 층부터 아래로 더해가면서 리스트 만들기

2. 2층까지는 선택지 없으므로 2층까지 리스트 만들기

3. 맨 왼쪽과 오른쪽은 선택지가 없고, 중간은 인덱스 기준으로 근처 둘 중 큰 값 더하기

def solution(triangle):
    answer = 0
    #윗줄
    tri_list=[triangle[1][0]+triangle[0][0],triangle[1][1]+triangle[0][0]]

    for floor in triangle[2:]:
        tmp=tri_list[:]
        for i in range(len(floor)):
            if i==0: #처음 바로 위 더하기
                tri_list[0]+=floor[i]
            elif i==len(floor)-1: #마지막 바로 위 더하기
                tri_list.insert(len(floor), tmp[-1]+floor[i])
            else: #중간은 큰 숫자 골라서 더하기
                tri_list[i]= max(tmp[i-1],tmp[i])+floor[i]
    return max(tri_list)

더 나은 답안

1. 2층까지 리스트 따로 만들지 않기

2. 이중 for문 range 방식으로 통일

def solution(triangle):
    for t in range(1, len(triangle)):
        for i in range(t+1):
            if i == 0:
                triangle[t][0] += triangle[t-1][0]
            elif i == t:
                triangle[t][-1] += triangle[t-1][-1]
            else:
                triangle[t][i] += max(triangle[t-1][i-1], triangle[t-1][i])
    return max(triangle[-1])

배운 점

1. 리스트를 복사할때는 깊은 복사를 써야함

 

참조

2023.01.13 - [파이썬] - [파이썬] 파이썬 리스트 복사하기