Algorithm/DP
-
백준 2096 내려가기Algorithm/DP 2022. 9. 16. 16:20
골드 5 난이도의 dp문제이다. 문제를 처음 읽으면 굉장히 간단한 dp문제로 보인다. max_dp[i][j] => i행 j열까지 내려왔을 때, 점수들의 합이 가장 큰 값 min_dp[i][j] => i행 j열까지 내려왔을 때, 점수들의 합이 가장 작은 값 1. 하지만 메모리 제한이 4MB이기 때문에, max_dp와 min_dp를 넉넉하게 최대값인 100001 * 4로 잡는 순간 메모리 초과가 뜨게 된다. 그래서 조금 더 생각을 해 보면, 딱 2개의 row만 필요함을 알 수 있다. 첫 row는 현재 행 까지의 최대(최소)값 들을, 다음 row는 해당 행 까지의 최대(최소)값을 넣어주고 다음 행을 조사하기 직전에, 마지막 row의 모든 값들을 첫 row로 이동 해 주면 되는 것이다. 따라서, 2 * 3 배열..
-
[프로그래머스] 정수 삼각형Algorithm/DP 2022. 1. 2. 19:10
https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr - 시간복잡도는 n = 삼각형의 높이라 할 때, n * (n-1) * (n-2) .. * 1 이므로 O(N^2)이다. - 간단한 DP문제이다. DP문제는 반드시 점화식을 세워야 한다. i를 꼭짓점부터의 해당 층의 상대적인 위치, j를 그 층에서의 요소의 인덱스라 할 때, 점화식은 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] (i, j = 0,1,...n) 단, 예외로 해당 층의 ..
-
백준 2839 설탕 배달Algorithm/DP 2021. 11. 13. 04:54
https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net - 2가지의 풀이법이 있다. Greedy, DP - Greedy 풀이법을 보면, 주어진 N에 3을 빼주면서, 뺄 때마다 해당 수가 5의 배수인지를 확인한다. 5의 배수가 되는 순간 남은 모든 무게를 5kg 봉지로 해결하면 되므로 그것이 해답이다. #include using namespace std; int N; int main() { cin >> N; int ans = 0; while (N >= 0) { i..