다이나믹프로그래밍(DP)
-
백준 2293번: 동전 1다이나믹프로그래밍(DP) 2020. 11. 27. 13:49
https://www.acmicpc.net/problem/2293 1. 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.) 2. 알고리즘 키워드 - 다이나믹 프로그래밍 https://www.youtube.com/watch?v=2IkdAk1Loek #include #include #include using namespace std; #include #include // min #include #include #include #include #include #include #include #define MAX_SIZE 100 int coin[..
-
백준 12847번: 꿀 아르바이트다이나믹프로그래밍(DP) 2020. 11. 27. 12:05
www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (0 < n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define ..
-
백준 11053번: 가장 긴 증가하는 부분 수열다이나믹프로그래밍(DP) 2020. 11. 26. 18:30
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 히스토리 2020-03-22 ..
-
백준 1932번: 정수 삼각형다이나믹프로그래밍(DP) 2020. 11. 26. 18:30
https://www.acmicpc.net/problem/1932 키워드 - 다이나믹프로그래밍, 구현 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define CENDL "\n" #define ll long long #define c_reverse(s) reverse(s.begin(), s.end()) #define c_sort(s) sort(s.begin(), s.end()) #define print_vect..
-
백준 2916번: 자와 각도기다이나믹프로그래밍(DP) 2018. 10. 21. 17:25
https://www.acmicpc.net/problem/2916 1. 문제 2. 알고리즘키워드 - DP - 접근법0 과 입력 받은, 각도도 만들수 있는 각으로 해야한다.만들어진 각도를 재활용 하여 다른 각도도 만들 수 있다. 3. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX..
-
백준 14501번 : 퇴사다이나믹프로그래밍(DP) 2018. 8. 12. 16:19
https://www.acmicpc.net/problem/14501 1. 문제 2. 알고리즘키워드 - DP 3. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100#define INF 0x7fffffff#define CENDL "\n"#define ll long long #define c_r..
-
백준 1463번: 1로 만들기다이나믹프로그래밍(DP) 2018. 8. 9. 13:29
https://www.acmicpc.net/problem/1463 1. 문제 2. 알고리즘키워드 - 다이나믹프로그래밍, 메모제이션 3. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100#define INF 0x7fffffff#define CEN..
-
백준 1309번: 동물원다이나믹프로그래밍(DP) 2018. 8. 4. 17:41
https://www.acmicpc.net/problem/1309 1. 문제 2. 알고리즘키워드 - 다이나믹 프로그래밍 3. 코드 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100#define InF 0x7fffffff#define CEnDL "\n"#define ll long long int main() { cin.tie(0); std::io..