Overview
BOJ 1749번 점수따먹기 Python 문제 풀이
분류: Prefix Sum (누적합)
문제 페이지
https://www.acmicpc.net/problem/1749
풀이 코드 1
from sys import stdin
def main():
n, m = map(int, stdin.readline().split())
arr = [[0] * (m + 1)] + \
[([0] + list(map(int, stdin.readline().split()))) for _ in range(n)]
res = -10000
for i in range(1, n + 1):
for j in range(1, m + 1):
arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1]
for y in range(i):
for x in range(j):
res = max(arr[i][j] - arr[y][j] - arr[i][x] + arr[y][x], res)
print(res)
if __name__ == "__main__":
main()
pypy3 채점 결과는 통과하였지만, python3 채점은 시간초과가 발생한 코드이다.
4중 for문을 이용하여 탐색 시간이 오래걸린다.
바깥쪽 2중 for문을 이용하여 arr 리스트에 누적합을 구하여 저장한다. 그리고 현재 위치가 포함된 부분 행렬 중에서 합이 최대가 되는 값을 내부 2중 for문을 이용하여 구한다.
풀이 코드 2
from sys import stdin
def main():
n, m = map(int, stdin.readline().split())
arr = [[0] * (m + 1)] + \
[([0] + list(map(int, stdin.readline().split()))) for _ in range(n)]
res = -10000
for i in range(1, n + 1):
p = [0] * (m + 1)
for j in range(i, n + 1):
t = [0] * (m + 1)
for k in range(1, m + 1):
p[k] += arr[j][k]
t[k] = max(t[k - 1] + p[k], p[k])
res = max(t[k], res)
print(res)
if __name__ == "__main__":
main()
pypy3, python3 채점 결과 통과한 코드.
3중 for문을 이용하여 시간복잡도를 개선하였다.
안쪽 2중 for문에서, p 리스트에는 arr 리스트의 행 방향 누적합을 저장한다. 그리고 t 리스트에는 p 리스트의 열 방향 누적합을 저장한다. 단, t 리스트에 누적합을 저장할 때, 이전 누적값이 음수라면 버리고 p 리스트 값만 저장한다.
가장 바깥쪽 for문은 p 리스트에 저장할 누적합의 시작 지점을 지정한다. 만약 i가 3이라면 내부 2중 for문은 1, 2 행이 포함되지 않은 부분 행렬을 탐색하게 된다.
