Lesson 10. Prime and composite numbers - Flags #3 (속도 개선-2)

1. 속도 개선 아이디어

이전에 구했던 수식을 좀 더 살펴봐야 한다.

 

총거리(D) \( >= K * (K - 1) \)

 

위 식은 다음과 같이 정리할 수 있다.

\( D >= K * (K - 1) \)

\( D >= K^{2} - K \)

\( \textcolor{red}{D + K >= K^{2}} \)

 

여기서 \( D \) 와 \( K^{2} \)의 관계에 대해서 생각해보자.

\( \textcolor{red}{D + K >= K^{2}} \) 성립하기 위해서는, \( \textcolor{red}{\sqrt{D} >= K} \) 이어야 한다.

왜냐하면 \( \textcolor{red}{\sqrt{D} >= K} \) 이면, \( \textcolor{red}{D >= K^{2}} \) 이기 때문에, \( \textcolor{red}{D + K} \)는 항상 \( \textcolor{red}{K^{2}} \) 보다 커지기 때문이다.

---

그렇다면 \( \sqrt{D}  < K \) 이면, \( D + K >= K^{2} \) 성립할까?

정답은 '아니오' 이다.

예제를 통해서 확인해보자.

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]	A[10]	A[11]
1	5	3	4	3	4	1	2	3	4	6	2

Peaks: 1, 3, 5, 10

총 거리: 9

 

총 거리(D)는 9, 최대 Flag 수(K)는 4이다.

\( \sqrt{D}(3) < K(4) \) 참,

\( D(9) + K(4) >= K^{2}(16) \) 거짓, 모순이 발생한다.

그러므로, \( \sqrt{D}  < K \) 이면, \( D + K >= K^{2} \) 성립하지 않는다.

 

따라서 ,이 문제에서 찾아야 하는 것은 \( \textcolor{red}{\sqrt{D} >= K} \) 을 만족하는 K값 이다.

 

2. 문제해결 전략

• Peak 개수(K)를 구한다
• Peak 간 '총 거리(D)'를 구한다
• \( \sqrt{D} >= K \)을 만족하는 K를 구한다
• 구해진 K개를 기준으로, Flag를 꽂을 수 있는지 확인한다.

 

3. 코드 (C++)

#include <cmath>

int solution(vector<int> &A) {

    //peak 개수 구하기
    vector<int> peaks = {};
    for(size_t i = 1; i < A.size() - 1; i++)
    {
        if(A[i] > A[i - 1] && A[i] > A[i + 1])
        {
            peaks.emplace_back(i);
        }
    }

    //예외처리
    if(peaks.size() == 0) return 0;
    else if(peaks.size() == 1) return 1;

    //총 거리(D) 구하기
    int total_distance = 0;
    for(int i = 0; i < static_cast<int>(peaks.size()) - 1; i++)
    {
        int distance = peaks[i + 1] - peaks[i];
        total_distance += distance;
    }

    int K = static_cast<int>(peaks.size()); //최대 flag 개수
    int D = ceil(sqrt(total_distance)); //정수에서 정확한 제곱근을 구할 수 없다. 따라서 올림한다.
    while(D < K) //sqrt(D) >= K를 만족하는 K값 찾기
    {
        K--;
    }
    
    //실제 꽂을 수 있는, flag 수 구하기
    while(K > 0)
    {
        int flag_cnt = 1;
        int distance = 0;
        for(int i = 0; i < static_cast<int>(peaks.size()) - 1; i++)
        {
            distance += peaks[i + 1] - peaks[i];    
            if(distance >= K)
            {
                distance = 0;
                flag_cnt++;
            }
        }

        if(flag_cnt >= K) return K;
        K--;
    }

    return K;
}

 

 

4. 결과