다이나믹 프로그래밍2 BOJ 7579 - 앱 https://www.acmicpc.net/problem/7579 접근앱 중 최소비용으로 최대의 메모리를 확보하는 문제이다.휴대폰 메모리 M이 정해져있기 때문에, 냅색 문제로 해결할 수 있다.냅색 문제에서 weight와 value는 각각 앱의 비용과 앱의 메모리를 의미한다. 기존 냅색 문제에서 DP[i][j]의 의미는 i번째 앱 시점에서 j의 코스트로 가지는 최대 메모리 사용량이다.이중for문을 돌면서 DP[i][j]를 구하면된다. 그리고 마지막에 DP[i][j]가 M이상인 것 중 첫번째가 답이 된다.왜냐하면 i번째를 살펴볼때 j가 0부터 total(사용할 수 있는 최대 코스트)까지를 살피는 경우는 i번째 앱이 포함될 수도 있고 아닐 수도 있기 때문이다. 코드#include #include #inclu.. 2024. 7. 12. [👊DP뿌시기 #12] (BOJ 11660) 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3.. 2023. 8. 24. 이전 1 다음
