[Python] 백준 1932 : 정수 삼각형

문제

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

[ 문제 조건 ]

• 한 줄씩 내려가면서 합이 최대가 되는 경로 구하기
• 더해질 수 있는 값은 대각선 왼쪽 or 오른쪽

[ 해결순서 ]

1. 누적 값이 더해질 배열을 0으로 초기화 해서 입력받은 배열의 길이와 같게 선언 및 초기화 ( 그냥 입력받은 배열에다가 계산해도 무관하다 )
2. 예제를 분석하다 보니 가로 줄의 첫번째 값과 끝 값은 비교 대상이 없으므로 그냥 전 줄의 같은 인덱스 값을 더하면 되고,
3. 처음, 끝을 제외한 인덱스 값들은 이제 대각선 왼쪽 or 오른쪽을 비교해서 더 큰 값을 현재 값에 더해준다.
4. 그렇게 값을 누적시키면 맨 마지막 줄에 이제 여태까지 누적된 경우의 수가 배열에 저장
5. 그 중 최대 값을 구해 출력한다.

[ 예제 풀이 ]

✏️한줄평

: 약간의 인덱스 번호 헷갈림에 조금 걸렸지만 그래도 비교적 다른문제에 비해 빨리 풀었다. DP를 풀다보니 조금 감이 온 걸까... 그래도 분류를 모르고 풀었다면 시간이 더 걸렸을 것 같다. 문제 분류없이 빨리 푸는 그날까지... Keep.... Go..ing...

---

코드

	import sys
	input = sys.stdin.readline
	n = int(input())
	arr = [list(map(int, input().split())) for _ in range(n)]
	dp = [[0 for i in range(j+1)] for j in range(n)]
	dp[0][0] = arr[0][0]
	for i in range(1, n): #1부터 시작
	for j in range(i+1): #0부터 시작
	if j==0: #처음과 끝은 비교하지 않고 더함 (비교대상이 없음)
	dp[i][j] = dp[i-1][0] + arr[i][0]
	if j==i:
	dp[i][j] = dp[i-1][i-1] + arr[i][j]
	if 0<j<i:
	dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + arr[i][j]
	print(max(dp[n-1]))

view raw BOJ1932.py hosted with ❤ by GitHub