[백준] 1932 파이썬(python) : 정수 삼각형 - (★)

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

1932번: 정수 삼각형

 

 

각 행의 첫번째 원소와 마지막 원소는 그 바로위 원소들을 더해주면 되고 나머지들은 바로 위 2개의 원소들 중 큰 수를 더해준다.

 

import sys
n = int(sys.stdin.readline())
graph = [ list(map(int, input().split())) for _ in range(n)]
for i in range(1, n): #1
    for j in range(len(graph[i])): #2
        if j == 0: #3
            graph[i][j] = graph[i][j] + graph[i-1][j]
        elif j == len(graph[i])-1: #4
            graph[i][j] = graph[i][j] + graph[i-1][j-1]
        else: #5
            graph[i][j] = max(graph[i-1][j-1], graph[i-1][j]) + graph[i][j]
print(max(graph[n-1])) #6

 

#1 : dp[0]은 지정 값이라 생각하고 1부터 시작

#2 : 2중 for문을 사용하는데 그래프의 행마다 길이가 다르므로 각 행의 길이만큼 반복

#3 : 각 행의 첫번째 원소는 그 바로 위의 값을 추가해준다

#4 : 각 행의 마지막 원소는 그 바로 위의 값을 추가해준다

#5 : 첫번째도 마지막도 아닌 원소들은 자신의 위에 위치한 두 원소 중 큰 값을 선택해 더해준다

#6 : 모든 원소가 끝까지 내려올때 마지막 행에서 가장 큰 값을 출력한다

 

dp문제는 규칙성 찾기가 힘들다. 언제 적응될지 모르겠다.

 

다른풀이) 22.08.18

import sys
n = int(sys.stdin.readline())
graph = []
dp = [ [0]*n for _ in range(n) ] #1
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split()))) #2
dp[0][0] = graph[0][0] #3
for i in range(1, n): #4
    for j in range(len(graph[i])): #5
        if j == 0: #6
            dp[i][j] = dp[i-1][j] + graph[i][j]
        else: #7
            dp[i][j] = max(dp[i-1][j-1]+graph[i][j], dp[i-1][j]+graph[i][j])
print(max(dp[n-1])) #8

 

dp테이블을 만든 풀이다. 개인적으로 이 풀이가 더 마음에 든다

#1 : n*n크기의 dp테이블 0으로 초기화

#2 : 그래프에 값 입력

#3 : 반복문 1부터 시작하기 위한 dp[0][0] 초기화

#4 : 1부터 시작

#5 : graph[i]의 길이까지 반복

#6 : j == 0일때는 자신의 위에 있는 요소만을 받아줘야하므로 비교대상 없음

#7 : 자기위치의 graph값과 왼쪽위 오른쪽위 더한 값중 최대값으로 dp갱신

#8 : dp[0][0]으로 시작했으므로 dp[n-1] 중 가장 큰 값 출력