[Coding Test] 정수 삼각형

프로그래머스 코딩테스트 3단계 : 정수 삼각형

문제 설명

• 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

• 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

문제 풀이

• 이중 반복문을 통해 삼각형의 숫자 값들을 누적으로 더했을 때 더 큰 값으로 변경 ([[7], [10, 15], [18, 16, 15] ... ])
• 첫 번째 반복문의 범위가 1부터인 이유 : triangle[0][0] 은 값의 변화가 없기 때문
• 삼각형의 왼쪽 라인에 있는 값 (3, 8, 2, 4) = j 가 0인 값 들은 더할 수 있는 값이 바로 위에 있는 값 밖에 없으므로 triangle[i-1][j]를 더해줌 (if)
• 삼각형의 오른쪽 라인에 있는 값들(8, 0, 4, 5) 또한 더할 수 있는 값이 바로 위에 있는 값 밖에 없으므로 triangle[i-1][j-1]을 더해줌 (elif)
• 그 밖의 가운데 있는 값들은 두개의 값이 나타나기 때문에 두개 중 더 큰 값을 더해줌 (else)
• triangle의 마지막 줄에서 가장 큰 값을 출력

정답 코드

def solution(triangle):

    for i in range(1, len(triangle)):
        for j in range(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-1], triangle[i-1][j])

    return max(triangle[-1])

* 이 문제는 프로그래머스 코딩테스트 연습 3단계 문제입니다.