[🥲 프로그래머스] 정수 삼각형 - Dynamic Programming

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

코딩테스트 연습 - 정수 삼각형

 

✅ 내가 쓴 답

# 내 광탈한 풀이!!!!!
def solution(triangle):
    answer = []
    for i in range(len(triangle)):
        if i == 0:
            answer.append(triangle[i])
            continue
        temp = []
        for j in range(i-1, i):
            for idx, n in enumerate(triangle[i]):
                for idx2, m in enumerate(answer[j]):
                    if idx == idx2 or idx-1 == idx2:
                        temp.append(n+m)
            answer.append(temp)
    result = answer.pop(-1)
    return max(result)

삼각형으로 된 데이터가 있을때

1) 층을 기준으로

answer[i]는 triangle[i-1]을 더해준 후 저장.

2) 인덱스를 기준으로

양 대각선으로만 움직일 수 있으므로 인덱스는 같거나 1 차이일 경우만 해당

근데 강탈...!!!!!!!!!! 

 

✅ 남이 쓴 답

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])