https://www.acmicpc.net/problem/2839
1.문제 분석
어떤 N에 대해 3kg 가방과 5kg 가방 개수 조합이 여러개 있다고 하면 5kg 가방 개수가 더 많은 조합이 총 가방 갯수가 더 적을 것이다. 또한 N의 최대값이 5000밖에 안돼 모든 경우의 수를 다 고려해도 된다. 이때, 5kg 가방 개수가 적은 경우부터 찾기보다 많은 경우부터 찾는다면 정답은 더 빨리 찾을 수 있게 된다.
시간복잡도 계산
N의 최대값이 5000이기 때문에 N이 5000일때, 5kg가방 개수는 최악의 경우 0 ~ 1000개의 경우를 고려해야한다. 따라서 최대 시간 복잡도는 아래와 같다.
시간복잡도 = O(1,000)
2. 코드
#include<iostream>
using namespace std;
#define ERROR_CANNOT_HANDLE -1
#define ERROR_NO_NEED_MORE_BAG5 -2
int getNumOfTotalBag(const int numOfBag5, const int N) {
int leftWeight = N - (numOfBag5 * 5);
if (leftWeight < 0) {
return ERROR_NO_NEED_MORE_BAG5;
}
if (leftWeight % 3 != 0) {
return ERROR_CANNOT_HANDLE;
}
int numOfBag3 = leftWeight / 3;
return numOfBag5 + numOfBag3;
}
int main() {
int result;
int N;
cin >> N;
// 조금 더 빠른 검색을 위해, 5kg 가방이 많은 경우부터 고려한다.
for (int numOfBag5 = N / 5; numOfBag5 >= 0; numOfBag5--) {
result = getNumOfTotalBag(numOfBag5, N);
if (result >= 0) {
break;
}
}
cout << result << endl;
return 0;
}
'개발하고 > 코딩테스트' 카테고리의 다른 글
[백준] 2884번 알람 시계 (0) | 2023.07.15 |
---|---|
[백준] 1152번 단어의 개수 (0) | 2021.08.16 |
[백준] 1006번 제곱ㄴㄴ수 (0) | 2021.08.13 |
[백준] 1008번 A/B (0) | 2021.08.02 |
[백준] 1003번 피보나치 함수 (0) | 2021.08.02 |