파이썬 정수 삼각형(백준 BOJ 1932)
2022, Sep 24
문제
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
예제 입력 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
예제 출력 1
30
📝 풀어보기
📌 아래로 내려가는 삼각형은 크게 3가지로 구분된다.
- 누적되는 열이 0번째일 때
- 누적되는 열이 끝일 때
- 누적되는 열이 양쪽으로 갈라질 때
이 3가지의 계산을 누적해서 저장한 뒤에 제일 큰 값을 출력하면 된다.
📌 삼각형의 크기 n을 입력받고, 누적값을 저장할 리스트 dp를 생성한다.
n만큼 반복하면서 dp에 삼각형의 값을 리스트 형태로 저장받는다.
n = int(input())
dp = []
for i in range(n) :
dp.append(list(map(int,input().split())))
📌 삼각형의 행과 열을 기준으로 2중 리스트를 순회하면서
- j==0(순회하는 열이 0) 일때 0번째 열끼리 값을 누적시킨다.
- j==i(순회하는 열이 마지막) 일때 마지막 열끼리 값을 누적시킨다.
- 양갈래로 뻗어나갈 때
dp[i-1][j-1], dp[i-1][j] (왼쪽과 오른쪽)중 큰 값을 누적한다.
마지막으로 전부 누적된 n-1행에서의 최대값을 출력하면 최대가 있는 경로의 합을 구할 수 있다.
for i in range(1,n) : # 행을 기준으로 1, 2, 3, 4, 5
for j in range(0,i+1) : # 열을 기준으로 0, 1, 2, 3, 4, 5, 6
if j == 0 : # 순회하는 열이 0일때
dp[i][0] += dp[i-1][0] # 0열끼리 더하기
elif j == i : # 순회하는 열이 끝일때
dp[i][j] += dp[i-1][j-1] # 마지막 열끼리 더하기
else : # 양갈래로 뻗어나갈때
dp[i][j] += max(dp[i-1][j-1],dp[i-1][j]) # 두 화살표중 더 큰 경우 누적하기
print(max(dp[n-1])) # n-1행에서의 최댓값 출력
전체 코드
# 5
# 7 dp[0][0]
# 3 8 dp[1][0], dp[1][1]
# 8 1 0 dp[2][0], dp[2][1], dp[2][2]
# 2 7 4 4 dp[3][0], dp[3][1], dp[3][2], dp[3][3]
# 4 5 2 6 5 dp[4][0], dp[4][1], dp[4][2], dp[4][3], dp[4][4]
n = int(input())
dp = []
for i in range(n) :
dp.append(list(map(int,input().split())))
for i in range(1,n) : # 행을 기준으로 1, 2, 3, 4, 5
for j in range(0,i+1) : # 열을 기준으로 0, 1, 2, 3, 4, 5, 6
if j == 0 : # 순회하는 열이 0일때
dp[i][0] += dp[i-1][0] # 0열끼리 더하기
elif j == i : # 순회하는 열이 끝일때
dp[i][j] += dp[i-1][j-1] # 마지막 열끼리 더하기
else : # 양갈래로 뻗어나갈때
dp[i][j] += max(dp[i-1][j-1],dp[i-1][j]) # 두 화살표중 더 큰 경우 누적하기
print(max(dp[n-1])) # n-1행에서의 최댓값 출력