백준 BAEKJOON 29718번 줄줄이 박수 [PYTHON/파이썬]

 

 

 

 

 

백준 BAEKJOON 29718번 줄줄이 박수 [PYTHON/파이썬]

---

<문제 출처> (SILVER Ⅲ)

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

 

 

 

 

 

 

 

 

<풀이>

2차원 리스트에 대한 누적합을 이용하면 쉽게 풀 수 있다.

먼저 박수 횟수가 저장되는 clap 리스트에 입력 값을 받아준다.

그리고 2중 for문을 사용하여 박수 횟수에 대한 누적합을 S 리스트에 담아준다.

for i in range(1, N + 1):
    for j in range(1, M + 1):
        S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + clap[i][j]

예제 입력 1을 기준으로 누적합을 채운 리스트는 아래와 같이 작성된다.

이 누적합을 토대로 브실이가 정한 열의 개수 A만큼 박수 횟수의 최댓값을 구해주면 된다.

즉 마지막 행인 0, 4, 14, 18, 30을 활용하면 된다.

A = 2일 때,

- 열 1~2의 합 : 1 + 5 + 2 + 3 + 1 + 2 = 14 → S[-1][2] - S[-1][0] = 14 - 0 = 14

- 열 2~3의 합 : 5 + 2 + 3 + 1 + 2 + 1 = 14 → S[-1][3] - S[-1][1] = 18 - 4 = 14

- 열 3~4의 합 : 2 + 6 + 1 + 5 + 1 + 1 = 16 → S[-1][4] - S[-1][2] = 30 - 14 = 16

 

이것을 수행하기 위한 코드는 아래와 같다.

A = int(input())
max_result = 0

for i in range(len(S[-1]) - A):
    result = S[-1][i + A] - S[-1][i]
    max_result = max(result, max_result)

 

이 과정을 수행하면 최대값을 출력할 수 있다.

 

 

 

 

 

 

 

 

 

<코드>

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
clap = [[0] * (M + 1)]
S = [[0] * (M + 1) for _ in range(N + 1)]

for i in range(N):
    clap_row = [0] + list(map(int, input().split()))
    clap.append(clap_row)

for i in range(1, N + 1):
    for j in range(1, M + 1):
        S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + clap[i][j]


A = int(input())
max_result = 0

for i in range(len(S[-1]) - A):
    result = S[-1][i + A] - S[-1][i]
    max_result = max(result, max_result)

print(max_result)