DP(다이나믹 프로그래밍): 백준 15988 파이썬 1,2,3 더하기 3
문제: https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이: 이 문제는 '1,2,3, 더하기 1' 9095번 문제에서 n의 범위가 크게 늘어난 문제이다. 이 문제에 9095번 문제와 같은 코드를 제출하면 메모리 초과가 발생한다. 그래서 다르게 풀어야 하는데, 먼저 다이나믹 프로그래밍 기법으로 범위 내의 방법 수를 다 구해서 리스트 'd'에 모두 저장한 뒤에 각 테스트 케이스를 입력받아 리스트 'arr'에 그 결과를 저장한다. 입력받은 테스트 케이스를 모두 저장하고 있지 않고, 테스트 케이스에 ..
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 다..
