백준 DP
[baekjoon 2294] 동전 2- DP(동적 프로그래밍) (C++)
www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 주어진 동전의 값을 이용해서 목표한 값을 동전 개수의 합으로 나타내는 경우 중 최소한의 동전 개수를 출력한다. 동전의 값보다 작은 숫자는 만들지 못한다. 동전의 값보다 큰 숫자는 크기가 n인 동전으로 구성할 수 있다. 그리고 그 이후에 크기가 n보다 큰 동전으로 그 숫자를 구성할 수 있다면 동전의 개수는 줄어든다. 즉, 5를 동전 1, 2, 5로 만들 수 있는 경우를 생각해보면 동..
[baekjoon 1149] RGB거리 (DP) (C++)
www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제는 빨강, 초록, 파랑으로 칠해져 있는 집 적혀있는 숫자의 합이 최소가 되도록 구하는 것이다. 규칙은 i번째 집은 i-1번째 또는 i+1번째 집과 같은 색으로 칠해져 있으면 안 된다. 즉, 만약 1번을 뽑았으면 다음 차례엔 1번을 뽑지 못한다는 것이다. 나는 3중 dp배열을 통해서 문제를 해결하려 했다. dp[i][n]에서 n은 각각 1번째, 2번째, 3번째 집을 의미하며 각각을 선택했..
[baekjoon 2225] 합분해- DP(동적 프로그래밍) (C++)
www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 조건은 N, K가 주어졌을 때 N을 K개의 숫자로 구성하는 경우의 수를 구하는 것이다. 예시로 N이 2이고 K 또한 2이면 경우의 수는 3개로 (0,2), (1,1), (2,0)이다. (0을 포함하고, 1-2, 2-1은 각각 카운트된다.) DP 배열은 2차원 배열로 구성되며, DP[N][K]로 N을 K개로 구성하는 경우의 수를 저장해주었다. 또한 순서가 있는 경우의 수이므로 순열의 경우로 생각해야 하며, 세 자릿수의 순열은 3!이다. 네 자릿수는 4! DP[0][2] ~ DP[N][2]배열엔 각각 2개로 0부터 N까지 구하는 경우..
[baekjoon 11054] 가장 긴 바이토닉 부분 수열- DP(동적 프로그래밍) (C++)
www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이 문제를 풀기 전에 풀어보면 도움이 되는 두 문제이다. www.acmicpc.net/problem/11722 가장 긴 감소하는 부분 수열 www.acmicpc.net/problem/11053 가장 긴 증가하는 부분 수열 바이토닉 수열이란 증가-> 감소하는 수열이라고 한다. 예를 들어 1, 2, 3, 4, 3, 2, 1의 경우 배열 자체가 바이토닉 수열이고 길이는 7이다. 증가만 해도 되고, 감소만 해도 된다. 처음에 풀었을 때는..
[baekjoon 1912] 연속합 - DP(동적 프로그래밍) (C++)
www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제는 주어진 수열에서 연속으로 나열된 숫자의 합이 최대가 되는 경우(결괏값은 합의 최댓값)를 찾는 것이다. 점화식을 세우기 위해서 여러 케이스를 생각해보았다. 일단 합의 최댓값이 되려면 더해지는 수가 음수면 안될 것 같았다. -> 하지만 이 i번째 음수를 포함하고 i+1번째 수를 더해서 최댓값이 나올 수 있다. -> i+1을 더해서 최댓값이 성립되려면 i번째까지의 누적합이 양수인 경우다. (i번째 누적합이 음수일 경우 ..
[baekjoon 2579] 계단 오르기 - DP(동적 프로그래밍) (C++)
www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net - 규칙 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 위의 규칙을 통해 두 가지 식을 세울 수 있었다. 1. 도착점 기준으로 생각해보는 경우 도착점 전 계단을 밟고 온 경우 : 연속해서 계단 3개를 밟..