DP3 백준 12865 평범한 배낭 algorithm : dp 해설 dp [i][j] 정의 : 1 ~ i번째 까지 물품을 사용해서 무게 j를 만들 때 물건들의 가치의 최댓값 예제 4 7 6 13 4 8 3 6 5 12 1 2 3 4 5 6 7 13 0 0 0 0 0 13 0 8 0 0 0 8 0 13 0 6 0 0 6 8 0 13 14 12 0 0 6 8 12 13 14 dp배열에서 최댓값이 정답 dp[i][j]가 될 수 있는 경우는 item [i]를 사용하여 만들거나 사용 안 하는 경우 2가지가 있다 item을 사용해서 만들 때는 dp[i - 1][j - item [i]. first]를 만들 수 있는 경우에만 item을 사용하여 만들 수 있다 소스코드 #include #define LM 100000+10 #define INF 199999.. 2021. 6. 4. 백준 11055 가장 큰 증가 부분 수열 algorithm : dp 해설 이문제는 dp 중에서도 LIS문제이다. dp [i] 정의 : 배열 i번째 까지 arr [i]를 사용했을 때 최댓값 dp[1]에서 오는 경우와 dp [3]에서 오는 경우가 있다 이경우 중 더 큰 값에 arr [6]을 더하면 dp [6]이 된다 LIS경우 이문은 N 2021. 6. 3. 백준 1699 제곱수의 합 algorithm : DP 해설 dp는 최솟값을 구하는 문제이기 때문에 답이 될 수 없는 INF를 초기값으로 한다 DP [i] : i번째 수를 만들었을 때 제곱수 항의 최소 개수 1 2 3 4 5 6 7 8 9 10 1 2 3 2 3 INF INF INF INF INF i가 6일 경우에는 5에서 1의 제곱수인 1을 더하여 4를 만들거나 2에서 2 * 2의 제곱수를 더하여 6을 만드는 3 만드는 2가지 경우중 제일 작은 3이 dp [6]이 된다. 이처럼 i를 만들수 있는 경우의 수 중 만들었을 때 가장 작은 값이 dp [i]가 된다 #include #define LM 200000+10 #define INF 199999999 using LL = long long; using namespace std; int.. 2021. 6. 3. 이전 1 다음
