dp

문제 바로 가기 > 4384번: 공평하게 팀 나누기0/1 냅색 알고리즘으로, DP로 풀 수 있다.이 문제는 '부분집합의 합' 문제의 변형으로 볼 수 있다. 우리의 목표는 전체 무게의 절반에 가장 가까운 부분집합을 찾는 것이다.2차원 boolean 배열 dp를 사용합니다.dp[i][j]는 i명의 사람을 선택하여 정확히 j 무게를 만들 수 있는지 여부를 나타낸다 (true/false)알고리즘1. dp 배열 초기화: dp[0][0] = true (0명으로 0kg을 만들 수 있음)2. 각 참가자에 대해:1명부터 전체 인원의 절반까지 선택하는 경우를 고려가능한 모든 무게 조합을 계산하여 dp 배열 갱신for(int i=0; i0; j--){ for(int k=totalWeight; k>=weights..

문제 바로가기 > 12865번: 평범한 배낭 전형적인 0/1 냅색 알고리즘으로, DP로 풀 수 있다. 1. 초기화최대 무게 K를 수용할 수 있는 dp 배열을 선언하고, 크기를 K + 1로 설정하여 모든 인덱스를 0으로 초기화dp[j]는 무게 j일 때의 최대 가치를 저장2. 동적 프로그래밍을 통한 최대 가치 계산각 물건에 대해 반복을 수행, 물건의 무게를 weight, 가치를 valuedp 배열을 역순으로 갱신: 이는 각 물건을 한 번만 고려하도록 하여 중복을 방지dp[j] (무게 j에서의 최대 가치)는 dp[j] (현재 가치)와 dp[j - weight] + value (현재 물건을 추가했을 때의 가치) 중 더 큰 값으로 갱신j는 K부터 weight까지 감소하면서 계산3. 결과 출력dp[K]에 저장된 값..

문제 배낭문제(Knapsack) + 0/1 DP(Dynamic Programming) 문제이다.✔️ 문제 예시 1고객 수 목표 C가 12명이고, 2개의 도시가 있다.도시 1: 3원에 5명의 고객을 유치도시 2: 1원에 1명의 고객을 유치✔️  DP 배열 초기화 및 정의dp의 길이는 C+100까지있다.딱 C일때의 값이 아닌 C를 넘기만 하면 되기 때문 (비용의 최댓값이 100이므로 C+100)dp[i]는 정확히 i명의 고객을 유치하는 데 필요한 최소 비용을 나타낸다dp[0]은 0으로 초기화되고, 나머지는 (C+100)*100으로 초기화를 한다.-> 각 비용의 최댓값이 100이기 때문이다.❗️주의해야 할 점최솟값을 구할 때 적어도 C를 넘어야 하는 거지 딱 C일때의 최솟값을 구하는 건 아니므로  C~C+10..