[그리디 알고리즘] 2839번 설탕배달 풀이(파이썬)

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 백준에 제시된 문제 풀이와 스스로 얻은 정보를 정리하고자 합니다.

그러므로 단순히 문제를 푸는 것이 중요한 것이 아니라, 문제를 통해 얻어가는 것이 있어야하기 때문에 접근 방식은 이전 기초 300제를 풀었을 때랑 동일합니다.

 

[접근 방식]

- 문제에서 요구하는 역량은 무엇인지?

- 알고 있어야하는 지식은 무엇인지? 에 기반하여 풀이하고자 합니다.

 

- 백준 문제 링크입니다. : https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

[풀이 아이디어]

- 0이상의 정수이므로 행이 내려갈수록 최대값은 계속 커질 것이다(최악의 경우 이전과 동일)

- 각 값에 대한 접근 편의성을 위해 삼각형을 2차원 배열로 정렬하여 표현(triangle 리스트 생성)

- 삼각형 각 행의 가장 왼쪽에서 최대값은 경우의 수를 따질 필요 없이 맨 위부터 현재 위치까지 맨 왼쪽값의 합.

- 그 외 영역에선 경우의 수를 따져야하는데, 리스트 접근을 통한 계산을 위해 삼각형 내 각 행마다 끝에 0을 더해줄 것(계산을 위한 더미 값)
   (아래 작성한 특정 위치의 최대값을 구하는 공식을 활용할껀데, 맨 오른쪽에 0이 없을 경우 index range 에러 발생)
   (가장 왼쪽에서 진행했던 방식과 동일하게 처리해도 됨)

- 특정 위치에서 가능한 최대합을 저장하는 dp 리스트(2차원) 생성

- 더하는 방법을 고려했을 때,
특정 위치의 최대값 =  위 왼쪽 대각선의 최대값+현재 위치의 값 vs 위 오른쪽 대각선의 최대값+현재 위치의 값

import sys
input = sys.stdin.readline
n = int(input())
graph = [list(map(int,input().split())) for i in range(n)]
#각 위치에서 가능한 최대값을 저장하기 위한 dp 리스트 생성
dp = [[0]*(n+1) for i in range(n)]

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

감사합니다.