250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- MySQL
- DP
- 백준
- 머신러닝
- MinHeap
- classification
- dynamic programming
- machine learning
- AlexNet
- image processing
- IN
- Reinforcement Learning
- C++
- opencv
- 그래프 이론
- SIFT
- canny edge detection
- exists
- Python
- 인공지능
- sklearn
- BFS
- 강화학습
- 자료구조
- TD
- dfs
- clustering
- 딥러닝
- Mask Processing
- edge detection
Archives
- Today
- Total
JINWOOJUNG
[ DP - 2839 ] 설탕 배달(C++) 본문
728x90
반응형
접근법
Dynamic Programming의 가장 쉬운 문제이다.
직관적인 접근이 가능한데, 우리가 원하는 것은 3a+5b = Inupt을 만족하는 a,b에 대하여 a+b가 최소가 되는 경우를 찾고싶은 것이다. 또한, 만들 수 없는 조합일 때는 결과가 -1이야 하는것을 명심하면 된다.
단순히 a 혹은 b 만으로 Input을 나타낼 수 있는 경우도 고려해야 하기 때문에 2중 for 문에서 해당 조건만 고려하면 쉽게 접근 가능하다. 또한, 3a+5b = Input을 만족하는 a,b에 대해서 Result를 처음에 -1로 설정하고 -1인 경우는 그냥 a+b를 Result로, -1이 아닌 경우 기존 Result와 a+b 중 작은 값을 Result로 설정하면 된다.
정답
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int32_t s32_Result = -1, s32_Input, s32_Three, s32_Five;
cin >> s32_Input;
for (s32_Three = 0; 3 * s32_Three <= s32_Input; s32_Three++)
{
for (s32_Five = 0; 5 * s32_Five <= s32_Input; s32_Five++)
{
if (3 * s32_Three + 5 * s32_Five == s32_Input)
{
if (s32_Result == -1)
s32_Result = s32_Three + s32_Five;
else
s32_Result = min(s32_Result, s32_Three + s32_Five);
}
}
}
printf("%d\n", s32_Result);
return 0;
}
728x90
반응형
'백준' 카테고리의 다른 글
[ DP - 9095 ] 1, 2, 3 더하기 (1) | 2024.03.29 |
---|---|
[ DP - 1463 ] 1로 만들기(C++) (0) | 2024.03.25 |
[ 28217 ] 두 정삼각형(C++) (0) | 2024.03.24 |
[ 그래프 이론 - 24444 ] 알고리즘 수업 - 너비 우선 탐색 1 (0) | 2024.03.19 |
[ 정렬 - 11399 ] ATM (0) | 2024.03.17 |