https://leetcode.com/problems/minimum-rounds-to-complete-all-tasks/description/
리트코드 2244번 문제임
대략 일이 N개 있다고 한다면, 동시에 처리할 수 있는 횟수는 2회 또는 3회이고
이 '처리' 1번을 round라고 하고, 주어진 모든 일들을 처리할 수 있는 최소 라운드를 구해라 라는 문제임
정답은 맞았는데, 난 DP로 풀었고 discussion에서 공유되는 방법이랑 다름.
읽어도 이게 2와 3이니까 가능한 방법인지, 보편적으로 쓸 수 있는지 모르겠다
내가 알고 싶은 부분은 2와 3의 합으로 최소 횟수를 구하는 방법을 일반화한 어떤 개념이나 정리가 있는지 궁금함
즉 A를 { n1, n2, n3 ... n4 }의 최소 합으로 나타내는 방법...인듯
내가 수학 개빡대가리라 뭘 어캐 검색해야할지 모르겠다
아래는 내가 제출한 C++ 제출코드
class Solution {
public:
int minimumRounds(vector<int>& tasks) {
int n = tasks.size();
int max_len = 100001;
int round = 0;
unordered_map <int, int> task_count; // task_count[task] = count
for (int i = 0; i < n; i++)
task_count[tasks[i]]++;
vector<int> memo(max_len,0);
memo[1] = -1; memo[2] = 1; memo[3] = 1; memo[4] = 2;
for (int i = 5; i < max_len; i++)
memo[i] = min(memo[i - 2], memo[i - 3]) + 1;
for (auto i : task_count)
{
//cout << i.first << " " << i.second << endl;
int r = memo[i.second];
if (r == -1)
return -1;
round += r;
}
return round;
}
};
