-
1932. [Python]정수 삼각형Python_알고리즘/Silver I 2024. 4. 22. 19:47
1. 문제
https://www.acmicpc.net/problem/1932
1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- DP(다이나믹 프로그래밍)
3. 파이썬 코드
import sys # 많은 인풋 처리 input = sys.stdin.readline N = int(input()) # 숫자 저장할 리스트 num_list = [] # 숫자 저장 for _ in range(N): num_list.append(list(map(int,input().split()))) # 1 ~ N 까지 반복 for i in range(1,N): # i+1 까지 반복 for j in range(i+1): # 양 끝점일 경우 한 경우의 수만 더함 if j == 0: num_list[i][j] += num_list[i-1][j] elif j == i: num_list[i][j] += num_list[i-1][j-1] # 외의 경우 이전값 대각선 중 max 값 선택 else: num_list[i][j] += max(num_list[i-1][j-1], num_list[i-1][j]) # 최종 계산된 결과에서 max 값 추출 print(max(num_list[-1]))
4. 문제를 풀고난 후 생각
- 문제 자체가 굉장히 직관적인 문제로 양 끝점을 제외한 부분에서 이전 값들의 max 값을 선택하는 방식으로 bottom-up 으로 쌓아나간다.
- DP 문제의 기본적인 능력을 확인하는 문제 같다.
5. 문제를 푸는데 도움이 되는 지식
- DP(다이나믹 프로그래밍)
'Python_알고리즘 > Silver I' 카테고리의 다른 글
1105. [Python]팔 (0) 2024.06.20 11052. [Python]카드 구매하기 (0) 2024.05.20 1141. [Python] 접두사 (0) 2024.04.09 11279. [Python]최대 힙 (0) 2024.01.09 1946. [Python]신입 사원 (0) 2023.12.19