[Python] 11660 - 구간 합 구하기 (실버1)

1. 문제 설명

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

11660번: 구간 합 구하기 5

 

---

2. 아이디어

최악의 경우에 1024 * 1024 크기의 표에서 값을 100,000 구해야 하는데 제한 시간은 1초밖에 안 된다.

bfs를 사용해서 매번 연산과정을 거쳐 값을 구하는 건 너무 미련한 짓이다.

이런 문제는 곧 dp를 사용해서 풀이해야 함을 알 수 있어야 한다.

 

우선 N*N 크기의 리스트에 [n-1][n-1]을 기점으로으로 [0][0]까지의 모든 좌표에 구간합을 구한다.

그리고 input으로 받은 구간합을 구하려면 구역을 나누어서 약간의 덧뺄셈을 추가해주면 된다.

[1][2]좌표에는 [7][7]까지의 구간합의 값이 저장되어 있으므로, [4][6]까지의 구간합을 구하고 싶다면

노란색으로 칠해진 구역의 구간합을 빼주면 된다.

하지만 주의해야 할 점은 녹색 구역처럼 중복되는 곳이 있다면 값을 더해주어야 한다.

 

위의 아이디어를 사용하여 몇 가지 경우만 더 추가해주면 안정적으로 통과할 수 있다.

참고로 input = sys.stdin.readline을 안 해주면 시간초과가 나온다..^^

 

---

3. 코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
cache = [[0]*n for _ in range(n)]

def solution():
    cache[n - 1][n - 1] = board[n - 1][n - 1]

    for row in range(n-1, -1, -1):
        for col in range(n-1, -1, -1):
            if row == n - 1 and col == n - 1:
                continue
            elif row == n - 1:
                cache[row][col] = cache[row][col+1] + board[row][col]
                continue
            elif col == n - 1:
                cache[row][col] = cache[row+1][col] + board[row][col]
                continue
            cache[row][col] = cache[row+1][col] + cache[row][col+1] - cache[row+1][col+1] + board[row][col] 

    for _ in range(m):
        y1, x1, y2, x2 = map(int, input().split())
        if y2 == n and x2 == n:
            print(cache[y1 - 1][x1 - 1])
        elif y2 == n:
            print(cache[y1 - 1][x1 - 1] - cache[y1 - 1][x2])
        elif x2 == n:
            print(cache[y1 - 1][x1 - 1] - cache[y2][x1 - 1])
        else:
            print(cache[y1 - 1][x1 - 1] - cache[y2][x1 - 1] - cache[y1 - 1][x2] + cache[y2][x2])

solution()