[Baekjoon] 21921 블로그 - C++

> 문제

< 문제에 있는 사진, 어디서 많이 본 듯 하다 >

문제 링크 : 

https://www.acmicpc.net/problem/21921

21921번: 블로그

문제 요약 : 총 n개의 방문자 수가 주어질 때, x일간 방문한 최대 방문자수와 그 방문자수가 있는 구간의 개수를 구하여라.

---

> 풀이들

1. 첫 번째 풀이 : 구간 x 안에 있는 사람들의 합을 각각 구하고, 그걸 n - x + 1번만 반복하면 되는 줄 알았다. 하지만 시간 초과가 떠서 다른 방법을 생각해야만 했다. (시간 복잡도가 O(n-x+1) * O(x) => O(x*n)이 나와버림)
2. 두 번째 풀이 : 구간 x 안에 있는 사람들의 합을 DP를 이용해 구하면 O(1)만에 구할 수 있다. 
   arr[0]  = arr[0], arr[1] = arr[0] + arr[1], arr[2] = arr[2] + arr[1], ... 이런 식으로 가다 보면 i번째부터 i+x-1번째 사람까지의 합은 arr[i+x-1] - arr[i-1]이다. => O(1)만에 해결 가능!

전체 코드는 다음과 같다.

https://github.com/siejwkaodj/Problem-Solve/blob/main/Baekjoon/Silver%203/21921.cpp

GitHub - siejwkaodj/Problem-Solve

코드는 c++로 구현하였다.

---

> 느낀점

DP를 이용해 구간합을 O(1)만에 구한다는 점이 특징인 문제였다.

이전에 이 문제를 푼 것이 많은 도움이 되었다.

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5