https://www.acmicpc.net/problem/29718
29718번: 줄줄이 박수
첫 번째 줄에 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $(1 \le N,M \le 2\,000)$ 두 번째 줄부터 $N$개의 줄에 걸쳐 박수 횟수에 대한 정보가 주어진다. $i+1$번째 줄에는 $i$행 $1$열부터 $i$행 $M$열까
www.acmicpc.net
소스코드
풀이
★ 응원단이 앉아있는 열 별로 박수 횟수를 구해야 하는데, 연속되는 A열 중 가장 박수 횟수가 많은 곳을 찾아야 합니다.
★ 먼저 배열을 돌면서 열 별로 박수 횟수를 clap 리스트에 저장해줬습니다.
★ 그 후 슬라이딩 윈도우 알고리즘을 사용하는데, 연속된 A개의 열의 박수 횟수 합을 window라는 변수에 저장한 뒤, 이웃되는 열들 즉, 연속되는 A열이 2,3열이라면 1열과 4열을 빼고 더해주면서 최대값을 찾아갑니다.
예제 입력 1을 살펴보면
clap = [4, 10, 4, 12]가 들어가게 됩니다. 이때 A가 2이기 때문에 1~2열 박수 횟수 합, 2~3열 박수 횟수 합, 3~4열 박수 횟수 합을 중 최대 횟수를 출력하면 됩니다.
슬라이딩 윈도우 기법을 사용하게 되면 초기 window는 1~2열의 합인 14가 됩니다. 그 다음엔 2~3열을 구해야 하는데, 2열이 중복되는 것을 알 수 있습니다. 슬라이딩 윈도우 기법은 이러한 중복 값을 따로 계산하지 않고 살릴 수 있습니다. 그러므로 2열은 가만히 두고 1열을 빼고 3열을 더하면 2~3열의 박수 횟수(14)를 구할 수 있습니다. 마지막으로 3~4열의 합은 16이 됩니다.
'Algorithm > 2023 브실컵' 카테고리의 다른 글
| [백준 알고리즘] 29730번: 임스의 데일리 인증 스터디 (Python) (1) | 2023.11.09 |
|---|---|
| [백준 알고리즘] 29732번: Rick-Roll Virus (Python) (0) | 2023.11.09 |
| [백준 알고리즘] 29723번: 브실이의 입시전략 (Python) (0) | 2023.11.08 |
| [백준 알고리즘] 29716번: 풀만한문제 (Python) (0) | 2023.11.08 |
| [백준 알고리즘] 29734번: 집에선 안돼잉 (Python) (0) | 2023.11.08 |