인프런 커뮤니티 질문&답변
작성한 질문수
이 코드는 어떤가요
작성
·
238
0
import sys
sys.stdin=open("input.txt","rt")
n = int(input())
a = []
dp = [0] * (n+1)
for i in range(n):
a.append(list(map(int, input().split())))
a = sorted(a, key =lambda x: x[0])
for i in range(n):
dp[i] = a[i][1]
for i in range(1, n):
for j in range(i):
if a[i][2] > a[j][2]:
dp[i] = max(dp[i] , dp[j] + a[i][1])
print(max(dp))
역순으로 문제를 해결해보려다가 뭔가가 잘 안풀려서 그냥 정렬로 문제를 해결해보았습니다.
퀴즈
동적 계획법(Dynamic Programming)의 핵심 아이디어는 무엇일까요?
문제를 가능한 모든 경우를 탐색하여 최적해를 찾습니다.
현재 상태에서 가장 좋은 선택만을 따라갑니다.
큰 문제를 작은 부분 문제로 나누어 해결하고 그 해답을 재사용합니다.
데이터를 정렬하여 검색 성능을 최적화합니다.
