누적합 & 구현 | SW Expert Academy 2001번 파리 퇴치 | Python

created_at : 01 May 2024 - 4 mins read time
Tags: 누적합 구현

SW Expert Academy 2001번 파리 퇴치 | Python
- 🔎 문제 설명
  - 📌 문제 풀이 큰 틀
- 💻 내 코드
  - 1️⃣ 구현
  - 2️⃣ 누적합

SW Expert Academy 2001번 파리 퇴치 | Python
- 🔎 문제 설명
  - 📌 문제 풀이 큰 틀
- 💻 내 코드
  - 1️⃣ 구현
  - 2️⃣ 누적합

SW Expert Academy 2001번 파리 퇴치 | Python

📌 SW Expert Academy 2001번 문제 바로가기

🔎 문제 설명

💙 D2

- 난이도 ★★☆☆
- 누적합 / 구현

N과 M의 범위가 그렇게 크지 않아서 4중 for문으로도 충분히 풀 수 있는 문제다. 조금 더 커지면 누적합으로 풀어야할 듯하다. 그래서 통과한 풀이도 1) for문 구현, 2) 누적합 이렇게 2개다. 2차원 배열 누적합은 처음인데 처음 접하면 시간을 많이 잡아먹을 것 같다. 더 연습해서 익숙하게 해야겠다는 생각이 들었다!

📌 문제 풀이 큰 틀

✅ 구현
for문 돌릴 범위 제한

✅ 누적합
(0,0)에서부터의 누적합을 미리 돌리고 나중에 파리채의 크기에 해당하는 합만을 구한다.

💻 내 코드

1️⃣ 구현

T = int(input())

for t in range(T):
    N, M = map(int,input().split())
    graph = [list(map(int, input().split())) for _ in range(N)]
    
    ans = 0
    deads = []

    for i in range(N-M+1):
        for j in range(N-M+1):
            dead = 0
            for k in range(M):
                for l in range(M):
                    dead += graph[i+k][j+l]
            deads.append(dead)

    print(f'#{t+1} {max(deads)}')'

2️⃣ 누적합

T = int(input())

for t in range(T):
    N, M = map(int,input().split())
    graph = [list(map(int, input().split())) for _ in range(N)]
    
    ans = 0
    prefixsum = [[0 for _ in range(N+1)] for _ in range(N+1)]

    for i in range(1, N+1):
        for j in range(1, N+1):
            prefixsum[i][j] = graph[i-1][j-1] + prefixsum[i-1][j] + prefixsum[i][j-1] - prefixsum[i-1][j-1]

    for i in range(N-M+1):
        for j in range(N-M+1):
            dead = prefixsum[i+M][j+M] - prefixsum[i][j+M] - prefixsum[i+M][j] + prefixsum[i][j]
            ans = max(dead, ans)

    print(f'#{t+1} {ans}')

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).