백준 14922번 부분평균

문제 링크입니다: https://www.acmicpc.net/problem/14922

힌트가 핵심인 문제였습니다.

구간이 1인 경우는 자기자신 뿐이므로 평균을 구할 수 없습니다.

구간이 2인 경우에는 P+1 == Q 이므로 힌트가 성립하지 않습니다.

구간이 3인 경우에는 P+2 == K+1 == Q이므로 힌트가 성립하지 않습니다.

구간이 4 이상인 경우에는 힌트가 성립하므로 평균이 더 작은 구간으로 나눌 수 있기 때문에 답은 구간이 2와 3 중에 있습니다.

따라서, 구간이 2 또는 3인 구간에서 평균이 제일 작은 구간의 P를 출력해주면 되는 문제였습니다.

주의할 점은, 구간이 3인 부분부터 구한 뒤에 구간이 2인 부분을 구해줘야한다는 점입니다!

#include <iostream>

using namespace std;

 

const int MAX = 1000000;

 

int N;

double A[MAX];

 

int startIdx(void)

{

        //구간의 길이 1: 성립 X

        //구간의 길이 2: P + 1 == Q 이므로 힌트 성립 X

        //구간의 길이 3: P + 2 == K + 1 == Q 이므로 힌트 성립 X

        //이후부터는 힌트 성립하므로 구간의 길이가 2 or 3이여야지만 성립

        double minAverage = (A[0] + A[1]) / 2;

        int idx = 0;

 

        //구간의 길이 3

        for (int i = 2; i < N; i++)

        {

                 double temp = (A[i - 2] + A[i - 1] + A[i]) / 3;

                 if (temp < minAverage)

                 {

                         minAverage = temp;

                         idx = i - 2;

                 }

        }

        //구간의 길이가 2

        for (int i = 1; i < N; i++)

        {

                 double temp = (A[i - 1] + A[i]) / 2;

                 if (temp < minAverage)

                 {

                         minAverage = temp;

                         idx = i - 1;

                 }

        }

        return idx;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상 위해

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> A[i];

 

        //배열의 길이 2: A(0~1)

        if (N == 2)

                 cout << 0 << endl;

        else

                 cout << startIdx() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~