knight7024   2년 전

제가 이 문제를 정확히 이해한게 맞나요?

5 3

1 2 3 4 5


1,2,3

1,2,3,4

1,2,3,4,5

2,3,4

2,3,4,5

3,4,5

이렇게 K개 이상을 묶어서 평균을 내고 표준 편차를 구하는 문제로 알고 있습니다.

그래서 누적합을 이용하여 합들을 관리했습니다.

그 외 평균을 내거나 표준 편차를 구하는 방법은 다른 분들과 마찬가지일거라 생각합니다.

예제는 모두 맞는데 제가 미처 생각지 못한 부분이 있다면 알려주세요.

seico75   2년 전

20번째줄 K로 나누는 것이 맞나요?

tempPrefix = prefixSum[x-1];  로 하는 것이 어떨까 합니다.

분산은 sum( (ns[i] - m)* (ns[i] - m)) = sum( ns[i]* ns[i] ) - m*m 입니다.

따라서 ns[i] 뿐 아니라 ns[i]* ns[i] 의 부분합을 구해두면 분산도 O(1)에 구할 수 있습니다.

knight7024   2년 전

아이고 K가 아니라 count네요 수정했음에도 틀렸다고 나오는건 마찬가지였습니다..

곱셈 공식을 응용할 수도 있었군요.. 구조를 아예 다시 짜야겠네요

이 소스는 포기해야할까봐요 ㅋㅋ

seico75   2년 전

18에서 count++ 을 하셨기 때문에 count 로 나누시면 안됩니다.

++/-- 연산은 수식 중에 넣으면 (휴먼) 오류가 잘 나는 것 같아요..

저라면 이런 식으로 해볼것 같습니다.

    for (int x = 1; x <= N - K + 1; x++)
    {
        for (int i = K + x - 1; i <= N; i++)
        {
            long double count = i - x + 1;
            long double m{ (prefixSum[i] - prefixSum[x-1]) / count}, A{};
            for (int j = x; j <= i; j++) A += (Ns[j] - m) * (Ns[j] - m);
            minA = min(minA, A / count);
        }
    }
    minA = sqrt( minA);


knight7024   2년 전

아래와 같이 수정해서 AC 받았습니다!!

prefixSum[i] - tempPrefix 부분이 문제였나 봅니다. 생각을 다시 해봐야겠어요..

댓글을 작성하려면 로그인해야 합니다.