[프로그래머스 lv 3] 정수 삼각형

사용 언어 - Python3

문제 - 정수 삼각형

프로그래머스

 

 

 

정답

DP 규칙 찾기 (정답 맞춘 여부 X) 

행, 열을 전부 돌면서 해당 위치의 값과 윗 값을 더해 가장 큰 값으로 해당 위치를 업데이트해준다.

가장 윗 값은 더할 것이 없으므로 무시하고 인덱스 1부터 시작한다. (실제론 2행부터 시작)

 

1. 삼각형의 가장 왼쪽 열 = 오른쪽 값만 더하기

2. 삼각형의 가장 오른쪽 열 = 왼쪽 값만 더하기

3. 나머지 값 = 양쪽 값 중에 큰 값으로 더하기

삼각형 마지막 행들 중 가장 큰 값을 return 한다.

def solution(triangle):
    for i in range(1,len(triangle)): # 행
        for j in range(i+1): # 열
            if j == 0: # 가장 왼쪽
                triangle[i][j] = triangle[i][j] + triangle[i-1][j] #오른쪽 값만 더하기
            elif j == i: # 가장 오른쪽
                triangle[i][j] = triangle[i][j] + triangle[i-1][j-1] #왼쪽 값만 더하기
            else:
                triangle[i][j] = triangle[i][j] + max(triangle[i-1][j],triangle[i-1][j-1]) # 둘중 큰 값 더하기

    return max(triangle[-1])

 

 

 

레퍼런스

• 정답 풀이

[Programmers]Lv 3. 정수 삼각형

• 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부