알고리즘 문제
[백준] 1932번 정수 삼각형
feelcoding
2020. 1. 18. 16:50
728x90
단계별로 풀어보기 동적계획법1의 6단계 문제
1932번: 정수 삼각형
문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는
www.acmicpc.net
이렇게 bfs로 풀어서 제출했는데
n = int(input())
from sys import stdin
li = []
for i in range(n):
li.append(list(map(int, stdin.readline().split())))
sum = []
import collections
q = collections.deque()
q.append((0, 0, li[0][0]))
while q:
cur = q.popleft()
if cur[0] == n - 1:
sum.append(cur[2])
else:
q.append((cur[0] + 1, cur[1], cur[2] + li[cur[0] + 1][cur[1]]))
q.append((cur[0] + 1, cur[1] + 1, cur[2] + li[cur[0] + 1][cur[1] + 1]))
print(max(sum))
메모리 초과로 실패
그래서 삼각형 아랫쪽부터 위로 올라오는 방식으로 동적계획법을 사용한 코드로 바꾸었다.
n = int(input())
from sys import stdin
li = []
for i in range(n):
li.append(list(map(int, stdin.readline().split())))
li[i].extend([0] * (n - 1 - i))
for i in range(n - 2, -1, -1):
for j in range(i + 1):
li[i][j] = max(li[i][j] + li[i + 1][j], li[i][j] + li[i + 1][j + 1])
print(li[0][0])
성공
728x90