dynamic programming (3) 썸네일형 리스트형 1005 ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net DP라기 보다는 위상 정렬에 더 무게를 둔 문제이다. 각 건물의 선행 건물들과 선행 건물의 수를 그 건물에 대응되는 배열의 위치에 저장한 후 큐를 이용하여 건물들을 짓는 것에 조건을 만족하며 소요되는 최소 시간을 계산하는 방식으로 해결하였다. 더보기 더보기 #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullpt.. 55 Jump Game Jump Game - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 배열의 i번째 위치에 도달할 수 있다면 i 이전의 모든 위치를 지날 수 있다는 점을 이용하면 간단하게 풀 수 있다. 솔직히 그냥 위 생각만 가지고 의식의 흐름으로 대충 풀었을 때 그냥 풀리는 수준의 난이도라 개인적으로 왜 Easy가 아니고 Medium인지 이해가 안 되는 문제였다. 더보기 더보기 class Solution { public: vector check; vector vec; bool .. 2228 구간 나누기 다이나믹 프로그래밍으로 해결해야 하는 knapsack 계열의 문제이다. vec = vector(n + 1); dp = vector(n + 1, vector(m + 1, -1)); 먼저 배열이 저장될 벡터 vec와 메모라이즈 된 값이 저장될 벡터 dp를 만들어주었다. 여기서 dp[i][j]의 의미는 i번째 배열까지 탐색했을 때, j개의 구간으로 조합했을 때의 최댓값을 나타내며, 메모라이즈 여부를 확인하기 위해서 -1로 초기화하였다. int search(int n, int m) { if (m == 0) return 0; if (n 0; --i) { partial_sum += vec[i]; temp = partial_sum + search(i - 2, m - 1); if (temp > dp[n][m]) dp[.. 이전 1 다음
