[백준] 낚시 30461번 Python

문제

건덕이는 일감호에 딸린 작은 섬, 와우도에 앉아 세월을 낚아 올리는 중이다.

 

일감호는 N*M 공간으로 나타낼 수 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있고, 각 칸에는 물고기가 여럿 존재한다. 가장 수심이 깊으면서 건덕이로부터 가장 먼 칸은 (N, M)이다.

건덕이는 낚싯대를 휘둘러 원하는 칸에 미끼를 던질 수 있다. 무게가 a인 무게추를 매달아 b만큼의 힘으로 낚싯대를 휘두르면 (a, b) 칸에 미끼가 존재하게 된다.

미끼는 일감호 공간 안에서 물고기들을 사로잡는데, 그 대상은 미끼가 속한 칸으로부터 수면까지 존재하는 모든 칸에 있는 물고기들이다. 즉, (a, b)에 존재하는 미끼는 1≤ i ≤ a인 모든 정수 i에 대해서 (i, b)$에 존재하는 모든 물고기를 사로잡는다.

건덕이가 낚싯줄을 한 바퀴 감아올리면, (a,b)에 위치한 미끼는 (a-1,b-1)로 이동하며, 이동한 위치에서 물고기를 사로잡는다. 미끼가 일감호의 공간을 벗어나면 즉시 회수된다.

건덕이가 무게추의 무게와 낚싯대를 휘두를 힘을 알려줄 때마다, 낚싯대를 휘두른 뒤 회수할 때까지 낚싯줄을 감아올리면 몇 마리의 물고기가 사로잡힐지 구해줘야 한다. 건덕이가 많은 물고기를 잡을 수 있도록 도와주자!

입력

첫째 줄에 일감호의 크기를 나타내는 정수 N,M과 건덕이가 낚싯대를 휘두를 횟수 Q가 공백으로 구분되어 주어진다.

(1≤N, M≤2000; 1≤Q≤300000) 

둘째 줄부터 N개의 줄에 걸쳐 각 공간에 존재하는 물고기의 수 Aij가 주어진다. N개의 줄 중 i번째 줄에 있는 j번째 수는 (i,j) 칸에 물고기가 Aij 마리 존재한다는 의미다. (0≤ Aij≤500)

 N+2번째 줄부터 Q개의 줄에 걸쳐 건덕이가 미끼에 매달 무게추의 무게를 나타내는 정수 Wi와 낚싯대를 휘두르는 힘을 나타내는 정수 Pi가 공백으로 구분되어 주어진다. (1≤Wi≤N; 1≤Pi≤M)

출력

 Q개의 줄에 걸쳐, 각 낚시에 대해서 미끼를 회수할 때까지 몇 마리의 물고기가 사로잡히는지 출력한다.

출처

University > 건국대학교 > 2023 건국대학교 프로그래밍 경진대회 (KUPC) > Division 1 D번

University > 건국대학교 > 2023 건국대학교 프로그래밍 경진대회 (KUPC) > Division 2 H번

University > 건국대학교 > 2023 건국대학교 프로그래밍 경진대회 (KUPC) > Open Contest H번

! 문제 생각&풀이 !

대각 + 세로의 누적합 문제라고 생각했다. 바로 로직 구현에 들어갔으나 내가 생각한 로직과 나오는 출력 값이 일치하지 않아 생각하는 시간이 길어졌다. 자바 고수분의 힌트를 제공받아 누적합의 배열을 먼저 생각해보았고 그 누적합의 배열에서 해당 좌표를 뽑아내면 되겠다고 생각했다. 

! Code ! (처음 제출한 코드)

# 낚시 G4
import sys

def solve():
    global arr, result

    # 각 행마다 물고기 수 집어넣기
    for i in range(1, N+1):
        # i번째 행의 1열부터 M번열까지
        arr[i][1:M+1] = map(int, sys.stdin.readline().rstrip().split())
        # print(arr)

    # 세로 누적 합 구하기
    for j in range(1, M+1):
        fish_sum = 0    # 물고기 누적 수
        for i in range(1, N+1):
            fish_sum += arr[i][j]
            # 물고기 누적 합을 배열에 넣기
            result[i][j] = result[i-1][j-1] + fish_sum

N, M, Q = map(int, sys.stdin.readline().rstrip().split())
arr = []
for _ in range(N+1):
    arr.append([0] * (M+1))

result = []
for _ in range(N+1):
    result.append([0] * (M+1))

# print(arr)
# print(result)

solve()
# print(result)
# for x in result:
#     print(x)

for _ in range(Q):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    print(result[a][b])

! Code ! (시간 단축 import io, os, sys 활용)

import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def solve():
    global arr, result
    for i in range(1, N + 1):
        arr[i][1:M + 1] = map(int, input().split())

    for j in range(1, M + 1):
        fish_sum = 0
        for i in range(1, N + 1):
            fish_sum += arr[i][j]
            result[i][j] = result[i - 1][j - 1] + fish_sum


N, M, Q = map(int, input().split())
arr = []
for _ in range(N + 1):
    arr.append([0] * (M + 1))

result = []
for _ in range(N + 1):
    result.append([0] * (M + 1))

solve()
for _ in range(Q):
    a, b = map(int, input().split())
    print(result[a][b])