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 ..
-
백준 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..
-
1143. Longest Common Subsequence릿코드(LEETCODE) 2020. 2. 15. 17:06
https://leetcode.com/problems/longest-common-subsequence/ 입력이 아래와 같을 때 text1 = "abcde", text2 = "ace" a b c d e a 1 1 1 1 1 a -> ace c 1 1 2 2 2 c -> ace e 2 2 2 2 3 e -> ace Source class Solution { public: int dp[1001][1001]; int longestCommonSubsequence(string text1, string text2) { int sol = 0; for (int i = 1; i
-
백준 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..
-
프로그래머스 Level 3 > 2 x n 타일링프로그래머스(Programmers) 2018. 7. 3. 20:30
https://programmers.co.kr/learn/courses/30/lessons/12900 1. 문제전형적인 타일링 갯수 세는 문제 2. 알고리즘키워드 - 다이나믹 프로그래밍프로그래머스 알고리즘 문제 개선으로 인하여 효율성 및 테스트 조건 추가 됨 3. 코드 123456789101112131415161718#include #include using namespace std; int solution(int n) { int answer = 0; int dp[600001] = {0,}; dp[1] = 1; dp[2] = 2; for(int i=3; i
-
백준 1912번: 연속합다이나믹프로그래밍(DP) 2018. 7. 3. 10:07
https://www.acmicpc.net/problem/1912 1. 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 2. 알고리즘키워드 - 다이나믹프로그래밍, 브루트 포스 * 접근초기 문제를 풀때 부르트포스로 해결 했었는데. 7달 뒤 보니 채점 기준이 달라져서 시간 초과 되었다. 입력 받는 수열 에서이전 값과의 합이 더크 다면 현재 dp 에 dp[i - 1] + dp[i] 저장 이전 값과의 합이 작다면 현..