[백준] 2839번 설탕 배달 (C++) - 간단한 dp
2023. 3. 22. 16:13
solving/C, C++
1. 발상 우선 아이디어는 다음과 같다. 설탕 5kg, 3kg이 있으므로 -> 이번 회차의 최소 설탕봉지 개수는 (이번회차-3) / (이번회차-5) 둘 중 최솟값을 구해 거기에 +1봉지를 더한 값이다. base case : dp[3] = 1, dp[5] =1, 모든 dp 배열의 값은 0으로 초기 설정한다. 예외 존재) dp[i-3], dp[i-5] 둘 중 하나만 가능한 경우: 둘 중 존재하는 값 + 1 로 설정해야 한다. 예외처리를 위해 IF, ELSE IF, ELSE문 이용하였다. 2. 소스코드 #include #include #include using namespace std; int dp[5001] = {0, }; int main(){ cin.tie(NULL); ios::sync_with_stdio..