동적 계획법

다이나믹 프로그래밍(DP, 동적 계획법)

[11052] 카드 구매하기

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 🔎 해결 방법 예를 들어 민규가 구매하고자 하는 카드의 개수가 4개라면, 가능한 조합은 4 / 3 + 1 / 2 + 2 / 2 + 1 + 1 / 1 + 1 + 1 + 1 이므로 자연수의 분할로 접근하면 되는 줄 알았다. 그러면 각 경우는 위와 같이 계산하면 되는데 2 +2 가 문제였다. dp를 생각하지 못하고 2 + 2를 계속 p[2] + p[2]라고 계산하는 바람에 점화식을 세울 수 없었다. 하지만! ..

[2193] 이친수

문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 내 코드(C) #include #define MAX 1000000 int main(void) { int n; long dp[MAX]; dp[0]=0, dp[1] = 1, dp[2] = 1; scanf..

[2163] 초콜릿 자르기

https://www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net 💡 내 코드(C++) // [2163] 초콜릿 자르기 /*초콜릿을 결국 1x1크기로 다 쪼갠다면 경우의 수는 한가지 밖에 없는데 왜 ..

[2133] 타일 채우기

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.... www.acmicpc.net 💡 내 코드(C++) /*[2133] 타일 채우기*/ /*https://www.acmicpc.net/problem/2133*/ #include using namespace std; int main(void) { int n, sum = 0; int dp[31]; cin >> n; dp[0] = 0, dp[2..

[1912] 연속합

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 💡 내 코드(C++) /*[1912] 연속합*/ /*https://www.acmicpc.net/problem/1912 */ #include #include using namespace std; int main(void) { int n, max; int arr[100001], dp[100001]; cin >> n; for (int i = 0; i > arr[i]; } dp[0] ..

[1904] 01타일

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 💡 내 코드(C) #include int main(void) { int n; long dp[1000001] = { 0 }; dp[0] =..

[1463] 1로 만들기

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 🔎 해결 방법 ucpc 캠프 2일차 '다이다믹 프로그래밍' 에서 제일 처음으로 풀었던 문제. 캠프 때 풀지 못해서 집에와서 다시 도전해보았는데 틀렸습니다 계속 떠서 접을 뻔...ㅎ 내가 실수한 부분 c에서는 기본적으로 min, max함수를 제공하지 않기 때문에 반드시 매크로를 정의해주어야 한다. (예를 들어, #define min(a, b) (((a) > n; dp[0] = 0, dp[1] = 0; for(int i = 2 ; i