백준 DP (5) 썸네일형 리스트형 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(다이나믹 프로그래밍): 백준 13398 파이썬 연속합 2 문제: https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이: 1912번 연속합 문제에서 수를 하나 제거하는 경우가 추가된 문제이다. 수를 제거한 경우와 제거하지 않은 경우를 나누어 dp 배열을 생성하고 큰 수를 비교하면서 저장해 나가면 된다. 항상 느끼는 거지만 다이나믹 프로그래밍 문제는 코드는 정말 간단하지만 문제의 규칙, 점화식을 생각해내는 과정이 너무 어렵다. 정답: import sys input = sys.stdin.readline n =.. DP: 백준 11052 파이썬 카드 구매하기 문제: https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이: 카드 n개를 구매하면서 가장 비싸게 구매하는 금액을 출력하는 문제이다. 각 경우를 생각해보자. 카드 1개 살 때: 0 + 1 카드 2개 살 때: 0 + 2 1 + 1 카드 3개 살 때: 0 + 3 1 + 2 카드 4개 살 때; 0 + 4 2 + 2 1 + 3 금액 들을 dp 배열에 저장하고 배열의 최댓값을 출력해주면 된다. 정답: import sys input = sys.stdin.read.. 다이나믹 프로그래밍(DP) : 백준 9095 자바(Java) 1, 2, 3 더하기 문제: https://www.acmicpc.net/problem/9095 풀이: 규칙을 파악하고 모든 경우에 대해 계산한 값을 dp배열에 저장하고 입력받은 케이스를 출력하는 방식으로 풀었다. 규칙은 간단했다. 정수 1 1가지 정수 2 2가지 정수 3 3가지 정수 4 7가지 . . . 이렇게 내려가는데, 정수 4 = 정수 1 + 정수 2 + 정수 3 = 7가지 임을 알 수 있다. 이 규칙에 따라 dp 배열에 저장해주면 된다. 정답: import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int[] dp; static int[] arr; static .. 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 다.. 이전 1 다음
