본문 바로가기

연속합

(1)

DP(다이나믹 프로그래밍): 백준 1912 파이썬 연속합 문제: https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이: 항상 느끼는 거지만 다이나믹 프로그래밍 문제는 코드는 정말 간단하지만 규칙과 점화식을 생각해내는 과정이 너무 어렵다. 이 문제도 연속합을 어떻게 구하는지 생각해내는 게 어려웠고, 코드는 간단했다. 반복문을 돌려 dp 배열에 저장되어있는 앞 값들의 연속합 + 현재 값과 현재 값 중 큰 것을 골라서 dp 배열에 저장해나가면 된다. 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 다..

티스토리툴바