백준-11660(파이썬)

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

11660번: 구간 합 구하기 5

 

문제생각

앞서 풀었던 구간 합 구하기4랑 비슷하게 해결하면 될거라고 생각했습니다. 

그래서 가로 누적합 또는 세로 누적합을 구하고 주어진 구간에 따라 누적합을 더하고 구간이 아닌 부분의 누적합을 빼는 방식으로 다가가려고 하였습니다.

 

그런데 어디서부터 잘못된건지 시간초과가 어마어마하게 났습니다...

아래의 코드는 시간초과가 난 코드입니다.(이 외에도 시간초과가 난 코드들이 꽤 있습니다...ㅎ)

import sys
input=sys.stdin.readline

n, m=map(int, input().split())
n_list=[list(map(int, input().split())) for _ in range(n)]
cs_list=[[0]*(n) for _ in range(n+1)] # 세로 누적합

for y in range(0, n):
    for x in range(1, n+1):
        cs_list[x][y]=cs_list[x-1][y]+n_list[x-1][y]

for _ in range(m):
    x1, y1, x2, y2=map(int, input().split())
    print(sum(cs_list[x2][y1-1:y2])-sum(cs_list[x1-1][y1-1:y2]))

분명 되야하는데...

속으로 맞왜틀(맞는데 왜 틀리지?)를 엄청 외쳤습니다.

 

근데 생각해보니 cs_list를 만들 필요없이 n_list를 누적합 형식으로 만들 수 있던 것입니다.

그러면 cs_list에 공간을 할당하기 위해 했던 반복문 등이 필요가 없어졌습니다.

 

문제코드

import sys
input=sys.stdin.readline

n, m=map(int, input().split())
n_list=[[0]*n]
for _ in range(n):
    n_list.append(list(map(int, input().split())))

for y in range(0, n):
    for x in range(1, n+1):
        n_list[x][y]+=n_list[x-1][y]

for _ in range(m):
    x1, y1, x2, y2=map(int, input().split())
    print(sum(n_list[x2][y1-1:y2])-sum(n_list[x1-1][y1-1:y2]))

 

하지만 이번문제는 효율이 굉장히 떨어졌습니다.

아마 sum연산과 리스트 슬라이싱에서 시간이 잡아 먹힌 듯 합니다...

슬라이싱과 sum을 쓰지않고 누적합을 더하고 빼기만 해서 할 수 있읅거 같습니다.

 

문제를 푸는데 있어 부족함을 느낍니다. 좀 더 나은 방법을 생각해봐야 겠습니다..

 

"아직 실력이 부족하여 문제 해결에 있어 코드가 매끄럽지 못한 점 양해부탁드립니다..ㅎ"