[BOJ][Python]1932번 풀이

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

import sys
ssr = sys.stdin.readline

n = int(ssr())
t = [list(map(int, ssr().split())) for _ in range(n)]
dp = [[0]*(i+1) for i in range(n)]
dp[0][0] = t[0][0]
for i in range(1,n):
    for j in range(i):
        dp[i][j] = max(dp[i-1][j]+t[i][j], dp[i][j])
        dp[i][j+1] = dp[i-1][j]+t[i][j+1]
print(max(dp[-1]))

이번 문제는 그다지 훌륭한 풀이는 아닙니다만 뭔가 획기적으로 좋은 최댓값 판단 방법이 뭔지를 잘 모르겠더라구요. 다른 분들의 풀이를 좀 참고해봐야겠습니다.

 

문제 풀이는 dp입니다. 다만 그렇게 n이 크지 않아서 dfs나 bfs같은 방법을 사용해도 통과할 것 같긴합니다. 제가 푼 방법은 이중반복문을 이용해서 모든 경우를 다 구해서 그 중에서 최댓값을 출력시키는 방법을 사용했습니다. 예시 1을 기준으로 설명을 드려보면 7과 3을 더한 수를 배열에 저장하고, 7과 8을 더한 수를 배열에 저장하고 다음 인덱스로 넘어가서 7+3+8을 저장하고 7+3+1을 저장, 7+8+1 저장, 7+8+0 저장....을 쭉 반복해서 맨 아래까지 내려가면 우리가 선택할 수 있는 모든 경로에 대한 합이 나와있을 것입니다. 그 중에서 최댓값을 출력하는 것으로 문제를 해결했습니다. 다만 그렇게 하면 데이터가 아래로 갈수록 2배씩 늘어나기 때문에 중간에 겹치는 부분을 최댓값을 사용하도록 해서 각 행의 원소의 갯수가 최대 행 번호만큼만 나오도록 해주었습니다(dp[i][j] = max(dp[i-1][j]+t[i][j], dp[i][j]) 이 부분).시간도 넉넉하고 데이터도 적어서 실버 1도 살짝 높은게 아닌가 싶기는 해요.