[백준] 1932번 : 정수 삼각형 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1932번: 정수 삼각형

 

1. 문제 설명

2. 풀이과정

해당 문제는 올 수 있는 이전의 길의 결과 중 가장 최댓값을 계속 적으로 선택하여 오면 된다.

하여 처음부터 다음 길을 갈 때 다음 길에 지금까지 온 길의 합을 계속 저장하고, 마지막에 도착했을 때 마지막 길들 중 최댓값을 구하면 해결되는 문제이다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 삼각형의 크기를 입력받는다. n = int(sys.stdin.readline())
3. 삼각형을 저장할 리스트를 생성한다. triangle = list()
4. 삼각형 크기만큼 반복하며 for _ in range(n)
5. 각 삼각형 값을 입력받아 리스트로 추가한다. triangle.append(list(map(int, sys.stdin.readline().split())))
6. 각 경로를 내려올 때 최댓값을 저장할 리스트를 생성한다. result = list()
7. 먼저 출발점을 추가한다. result.append(triangle[0])
8. 출발점을 추가했으므로 크기에서 1을 뺀 결과만큼 반복한다. for i in range(len(triangle) - 1)
9. 각 가로열의 길의 결과를 저장할 리스트를 생성한다. li = list()
10. 다음 가로열의 개수만큼 반복하며 for j in range(len(triangle[i + 1]))
11. 만약 구하려는 가로열의 위치가 제일 앞이라면 if (j == 0)
12. 해당 위치의 이전 길은 무조건 이전 가로열 길의 제일 앞 길이다. 하여 이전 길의 값과 구하려는 다음 길의 값을 더하여 추가한다. li.append(result[i][j] + triangle[i + 1][j])
13. 만약 구하는 위치가 제일 뒷 길이라면 elif (j == len(triangle[i + 1]) - 1)
14. 이전 길은 무조건 이전 가로열 길의 제일 뒷 길이다.  하여 이전 길의 값과 구하려는 다음 길의 값을 더하여 추가한다. li.append(result[i][j - 1] + triangle[i + 1][j])
15. 반면에 구하는 위치가 중간 길이라면 else
16. 이전 길은 2가지의 선택지가 생긴다. 하여 이전 길의 2가지 선택지 값 중 더 큰 값을 가져와 다음 길의 값을 더하여 추가한다. li.append(max(result[i][j - 1], result[i][j]) + triangle[i + 1][j])
17. 각 가로열의 모든 길을 구했으면 구한 결과를 추가한다. result.append(li)
18. 마지막 가로열까지 각 길별 올 수 있는 최댓값의 경우를 구했으면 마지막 가로열 길의 값 중 최댓값을 저장한다. print(max(result[-1]))

반응형

3. 소스코드

import sys

n = int(sys.stdin.readline())

triangle = list()
for _ in range(n):
    triangle.append(list(map(int, sys.stdin.readline().split())))

result = list()
result.append(triangle[0])

for i in range(len(triangle) - 1):
    li = list()
    for j in range(len(triangle[i + 1])):
        if (j == 0):
            li.append(result[i][j] + triangle[i + 1][j])
        elif (j == len(triangle[i + 1]) - 1):
            li.append(result[i][j - 1] + triangle[i + 1][j])
        else:
            li.append(max(result[i][j - 1], result[i][j]) + triangle[i + 1][j])

    result.append(li)
    
print(max(result[-1]))