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 <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dp[5001] = {0, };
int main(){
cin.tie(NULL); ios::sync_with_stdio(false);
int N;
cin >> N;
dp[3] = 1;
dp[5] = 1;
for(int i=6; i<N+1; i++){
if(dp[i-3] > 0 && dp[i-5] > 0){
dp[i] = min(dp[i-3], dp[i-5]) + 1;
}
else if(dp[i-3] > 0 && dp[i-5] == 0){
dp[i] = dp[i-3]+1;
}
else if(dp[i-5] > 0 && dp[i-3] ==0){
dp[i] = dp[i-5]+1;
}
}
if (dp[N] != 0) cout << dp[N];
else cout << "-1";
}
DP 부분만 살펴보면 다음과 같다,
for(int i=6; i<N+1; i++){
if(dp[i-3] > 0 && dp[i-5] > 0){
dp[i] = min(dp[i-3], dp[i-5]) + 1;
}
else if(dp[i-3] > 0 && dp[i-5] == 0){
dp[i] = dp[i-3]+1;
}
else if(dp[i-5] > 0 && dp[i-3] ==0){
dp[i] = dp[i-5]+1;
}
}
dp[i-3], dp[i-5]의 값이 둘 다 존재할 경우 -> 둘을 비교하여 작은 값 + 1
dp[i-3]의 값만 존재할 경우 -> 해당 값에 +1
dp[i-5]의 값만 존재할 경우 -> 해당 값에 +1
if (dp[N] != 0) cout << dp[N];
else cout << "-1";
저장된 값이 있을 경우 (0이 아닐 경우) dp 배열에 저장된 값을,
저장된 값이 없을 경우 -1을 출력한다.
'solving > C, C++' 카테고리의 다른 글
[백준] 11660번 구간 합 구하기 5 (C++) - 간단한 dp (0) | 2023.03.21 |
---|---|
[백준] 1912번 연속합 (C++) - 간단한 dp (0) | 2023.03.21 |
[백준] 5639번 이진 탐색 트리 (C++) - binary search tree (0) | 2022.11.21 |
[백준] 1991번 트리 순회 (C++) - preorder, inorder, postorder (0) | 2022.11.21 |
[백준] 1325번 효율적인 해킹 - C++ (DFS, 그래프) (0) | 2022.11.10 |