[알고리즘] 프로그래머스 - 정수삼각형

da__ell·2023년 3월 27일
0

DataStructure / ALGORITHM

목록 보기
17/23

문제

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

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

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

제한사항

삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

풀이 해설

def solution(triangle):
    n = len(triangle)
    dp = [[0]*(i+1) for i in range(n)]
    dp[0][0] = triangle[0][0]

    for i in range(1, n):
        for j in range(i+1):
            if j == 0:
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            elif i == j:
                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
            else:
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

    answer = max(dp[n-1])
    return answer

동적 프로그래밍을 활용해서 문제를 해결하였다. 각 삼각형에서 이동할 때 얻을 수 있는 최댓값을 2차원 배열로 만들어 저장하는 방식이다.
그리고 각 배열의 값을 선택하는 방식은 3가지이다.

첫 번째는 (i행, 0열)에 위치해 있을 때다. 이 경우에는 i-1행 0열에서 밖에 타고 들어올 수 없기 때문에 해당 값에서 triangle의 해당 행, 열의 값을 더해주면 최댓값이 된다.

두 번째는 (i행, i열)에 위치해 있을 때다. i행 i열에 위치해 있다는 것은 해당 행의 가장 마지막 열에 위치해 있다는 것을 의미한다. 따라서 해당 (i-1)행과 (j-1)열에서만 이동이 가능하므로 해당 값에서 triangle의 해당 행, 열의 값을 더해주면 최댓값이 된다.

마지막은 그 외의 경우일 것이다. 삼각형의 이동경로는 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다고 되어있으므로 (i-1)행 (j-1)열 혹은, (i-1)행에서 j열에서 이동하는 경우가 있다. 이 중 최댓값을 선택해서 triangle의 해당 행, 열의 값을 더해주면 최댓값이 된다.

profile
daelkdev@gmail.com

0개의 댓글