https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 풀이 방법 다이나믹 프로그래밍 문제이다. 구해야 하는 것이 '적어도 C명을 늘이기 위한 최소 비용' 이다. 따라서 dp[i] 를 i명을 늘이기 위해 필요한 최소 비용으로 설정하였다. 그리고 for문으로 입력받은 홍보 비용과 고객 수를 순회하면서 해당 홍보 비용을 사용하여 만들 수 있는 모든 고객 수에 대해 dp 값을 갱신해주도록 한다. 현재 홍보 비용을 cost, 늘릴 수 있는 고객 수를 nu..
DP
https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 방법 다이나믹 프로그래밍 문제이다. 결국 N일이 모두 지난 후의 최대 수익을 구해주면 되므로 dp에 저장되는 값을 해당 날까지의 최대 수익으로 설정하여 갱신시켜나가면 되겠다고 생각했다. 따라서, 오늘이 i일이라고 할 때 dp[i] = i일까지 가장 많이 벌 수 있는 경우의 최대 수익이다. dp 배열은 N+2 크기로 생성한다. 이유는 N일까지 상담을 진행한 것은 ..
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 방법 다이나믹 프로그래밍을 사용하여 풀었다. dp 문제를 풀 땐 먼저 구하고자 하는 것이 무엇인지를 생각하는 것이 가장 쉬운 접근 방법인 것 같다. 구하고자 하는 것이 N개 카드 구매 시 지불할 금액의 최댓값이 이므로 DP 배열의 값을 각 구매 개수에 따른 지불 최댓값을 저장해야겠다고 생각했다. 즉, 카드 2개 구매 시 최댓값이 10이면 dp[2] = 10이 되는 것이다. 카드 구매 시 i번 카드팩..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 풀이 방법 다이나믹 프로그래밍을 사용한다. 1. k+1 길이의 dp 배열을 생성하고 100001 로 초기화한다. 1~k 까지의 가치를 인덱스로 하여 각 가치를 만들 수 있는 동전의 최소 개수를 저장한다. 즉, dp[5] 는 가치 5를 만들기 위해 필요한 동전의 최소 개수가 된다. 동전의 가치 입력 범위가 100000 이므로 +1 을 하여 초기화한다. 주의, dp[0..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 방법 반복문을 이용하여 다이나믹 프로그래밍의 bottom-up 방법으로 풀었다. 연속된 수의 합이므로 이전부터 계속 연속되는 경우와 지금부터 연속이 시작되는 두 경우를 비교하여 구하면 된다. 따라서 점화식은 dp[i] = max(dp[i-1] + arr[i], arr[i]) 가 된다. 예제를 통해 보자 1번: 10 (dp의 첫번째 값은 arr 값으로 초기화) 2번: 10 + (-4) > -4 이므로 6..
