[Week of DP] BOJ 11660 #2

사실 딱 문제를 보기에는

N의 최댓값이 1024이므로 1024 * 1024의 시간 복잡도로

무난히 성공할 것으로 보이지만(100,000,000 미만 이므로)

M이 100000이기 때문에 최악의 경우 100,000,000,000(천억)의 시간 복잡도를 가질 수 있기에

2중 for 문으로 M이 주어질 때마다 값을 구하는 건 TLE(Time Limit Exceeded)를 발생할 가능성이 크다.

 

그렇기에 주어진 배열의 구간합을 구한 뒤

특정 Index들의 합/차를 활용하여 출력을 하게 되면

1024 * 1024 + 100000의 시간 복잡도로 문제를 풀 수 있게 된다.

 

원래는 가로/세로의 구간합을 따로 구해서 문제를 풀어보려 했으나

직접 가로/세로 구간합을 따로 구해보니 세로 구간합을 활용할 방법이 딱히 떠오르지 않아서

전체 구간합을 구해서 푸는 방법을 시도해보았다.

 

일단 예제를 기준으로 전체 배열의 구간합을 구해보면

구간합을 구하는 공식을 정리하면

원래 배열을 ar, 구간합 배열을 sar, 현재 위치의 index를 x, y라고 했을 때

sar [x][y] = ar [x][y] + sar [x-1][y] + sar [x][y-1] - sar [x-1][y-1]

 

예를 들어 sar(2,2)의 값인 8은

sar [2][2] = ar [2][2] + ar [1][2] + ar [2][1] - ar [1][1] = 3 + 3 + 3 - 1 이 된다.

물론 sar [0][0~n] = sar [0~n][0] = 0으로 미리 초기값을 넣어놓아야 한다.

 

그리고 m(i, j, k, l)이 2, 2, 3, 4 인 경우

result = sar [k][l] - sar [i-1][l] - sar [k][j-1] + sar [i-1][j-1] = 42 - 10 - 6 + 1 = 27 이 된다.

위의 로직을 그대로 작성하면 다음과 같다.

if __name__ == "__main__":
    n, m = map(int, input().split(' '))
    ar = [[0 for _ in range(n+1)]]
    for __ in range(n):
        ar.append([0] + list(map(int, input().split(' '))))

    sar = [[0 for _ in range(n+1)] for __ in range(n+1)]
    for y in range(1, n+1):
        for x in range(1, n+1):
            sar[y][x] = ar[y][x] + sar[y][x-1] + sar[y-1][x] - sar[y-1][x-1]

    for __ in range(m):
        i, j, k, l = map(int, input().split(' '))
        result = sar[k][l] - sar[i-1][l] - sar[k][j-1] + sar[i-1][j-1]
        print(result)

그러나 이렇게 제출하면 TLE로 실패!! 가 된다.

아무래도 입출력 함수를 바꿔야 될 거 같아서(입출력이 많은 문제들은 이런 경우가 잦음)

아래 블로그를 참조해서 입출력 부분을 일부 수정했다.

 

breakcoding.tistory.com/109

 

from sys import stdin

if __name__ == "__main__":
    n, m = map(int, stdin.readline().split(' '))
    ar = [[0 for _ in range(n+1)]]
    for __ in range(n):
        ar.append([0] + list(map(int, stdin.readline().split(' '))))

    sar = [[0 for _ in range(n+1)] for __ in range(n+1)]
    for y in range(1, n+1):
        for x in range(1, n+1):
            sar[y][x] = ar[y][x] + sar[y][x-1] + sar[y-1][x] - sar[y-1][x-1]

    results = ''
    for __ in range(m):
        i, j, k, l = map(int, stdin.readline().split(' '))
        result = sar[k][l] - sar[i-1][l] - sar[k][j-1] + sar[i-1][j-1]
        results += str(result) + '\n'

    print(results)

 

오랜만에 설루션 검색 없이 내 힘으로 풀었던 문제!

아무래도 구간 합의 경우 dp 중에서도 제일 쉬운 case라..

그래도 뿌듯한 문제풀이였다.