링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43105
문제 설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한조건
- 삼각형의 높이는 1 이상 500 이하입니다.
- 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
코드
def solution(triangle):
dp = [([0]*len(triangle[-1])) for _ in range(len(triangle))]
dp[0][0] = triangle.pop(0)[0]
cnt = 1
for tmp in triangle:
for i in range(len(tmp)):
if i == 0:
dp[cnt][i] = dp[cnt-1][i] + tmp[i]
elif i == len(tmp):
dp[cnt][i] = dp[cnt-1][i-1] + tmp[i]
else:
dp[cnt][i] = tmp[i] + max(dp[cnt-1][i-1], dp[cnt-1][i])
cnt = cnt + 1
return max(dp[-1])
아이디어
1. 각 레벨에서 7 -> 4, 7 -> 5로 가는 루트는 문제섦명에서 우측, 좌측 대각선으로밖에 못가니 직선으로 밖에 못가서 계속 더한다.
2. 그 사이 공간의 것들은 이전 단계에서 현재 단계에 나로 올 수 있는 좌/우측 중 더 큰 값을 선택해 끝까지 더해간다. 즉, 현재 내 위치를 오는건 확정이면 이전단계에서 나로 올 수 있는 루트 중 더 큰 것을 더한다.
'알고리즘' 카테고리의 다른 글
프로그래머스 - 입국심사(43238) (0) | 2023.01.29 |
---|---|
백준 - 2064 IP주소 (0) | 2023.01.27 |
백준 - 부분합 (0) | 2023.01.09 |
백준 - RGB거리 (0) | 2022.12.20 |
프로그래머스 - 혼자 놀기의 달인 (0) | 2022.12.20 |