[백준] 24620번 : Sleeping in Class (C++)

24620번 : Sleeping in Class

---

문제)

Bessie the cow was excited to recently return to in-person learning! Unfortunately, her instructor, Farmer John, is a very boring lecturer, and so she ends up falling asleep in class often.

 

Farmer John has noticed that Bessie has not been paying attention in class. He has asked another student in class, Elsie, to keep track of the number of times Bessie falls asleep in a given class.

 

There are N class periods (1≤ N  ≤10^5), and Elsie logs that Bessie fell asleep a_i times (0≤ a_i ≤10^6) in the i-th class period.

 

The total number of times Bessie fell asleep across all class periods is at most 106$10^6$.

 

Elsie, feeling very competitive with Bessie, wants to make Farmer John feel like Bessie is consistently falling asleep the same number of times in every class -- making it appear that the issue is entirely Bessie's fault, with no dependence on Farmer John's sometimes-boring lectures.

 

The only way Elsie may modify the log is by combining two adjacent class periods. For example, if a = [1,2,3,4,5], then if Elsie combines the second and third class periods the log will become [1,5,4,5].

Help Elsie compute the minimum number of modifications to the log that she needs to make so that she can make all the numbers in the log equal.

 

 

 

입력 :

Each input will contain T (1≤ T ≤10) test cases that should be solved independently.

The first line contains T, the number of test cases to be solved. The T test cases follow, each described by a pair of lines. The first line of each pair contains N, and the second contains 1, 2,…, a_1, a_2,a_N.

It is guaranteed that within each test case, the sum of all values in a is at most 10^6. It is also guaranteed that the sum of N over all test cases is at most 10^5.

 

 

 

출력 :

Please write T lines of output, giving the minimum number of modifications Elsie could perform to make all the log entries equal for each case.

 

 

 

 

 

 

풀이)

정답 수열을 만드려면, 수열의 인자를 다 더한 값의 약수여야 한다는 것을 이용해 문제를 풀어주었다.

 

// 24620. Sleeping in Class
#include <iostream>
#include <vector>
#include <limits.h>
 
using namespace std;
 
int t, n;
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> t;
    
    while (t--)
    {
        cin >> n;
        vector<long long> vec;
        vec.resize(n + 1);
        long long _sum = 0;
        for (int i = 1; i < n + 1; i++)
        {
            cin >> vec[i];
            _sum += vec[i];
        }
 
        vector<long long> ali;
 
        for (long long i = 1; i * i <= _sum; i++)
        {
            if (_sum % i == 0)
            {
                ali.push_back(i);
                if (i * i != _sum) ali.push_back(_sum / i);
            }
        }
 
        long long ans = LLONG_MAX;
 
        // 해당 수열로 만들 수 있는 수들 (약수)
        for (int i = 0; i < ali.size(); i++)
        {
            long long cnt = 0;
            long long temp = 0;
            bool flag = false;
 
            // 수열을 돌면서 해당 약수를 만든다.
            for (int j = 1; j < vec.size(); j++)
            {
                temp += vec[j];
                cnt++;
 
                if (temp == ali[i] && vec[j] != 0)
                { 
                    temp = 0;
                    cnt--;
                }
                else if (temp > ali[i])
                {
                    flag = true;
                    break;
                }
            }
 
            if (flag == false)
            {
                ans = min(ans, cnt);
            }
        }
 
        if (ans == LLONG_MAX)
        {
            cout << "0" << '\n';
        }
        else cout << ans << '\n';
    }
 
    return 0;
}

---

출처 : https://www.acmicpc.net/problem/24620 

24620번: Sleeping in Class