[백준] 1749번 점수따먹기(python)(누적합)

 

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

1749번: 점수따먹기

 

1. 난이도 골드4 (🥇)

 

https://www.acmicpc.net/problem/11660 (구간 합 구하기5) 2차원 배열을 이용한다는 점에서 이 문제와 유사하나,

(x1,y1)부터 (x2,y2)까지의 경우에 가능한 x1,y1을 모두 확인해봐야 한다는 차이점이 존재한다.

 

1. 새로운 배열에 구간합을 구한다.

sum_num[i][j] = sum_num[i-1][j] + sum_num[i][j-1] - sum_num[i-1][j-1] + num[i][j]

 

2. 끝점을 for문으로 완전탐색하고, 시작점(처음부터 끝점까지)도 for문으로 완전탐색해서 총 4중 for문을 이용한다.

for x1 in range(1,n+1):
  for y1 in range(1,m+1):
    for x2 in range(1,x1+1):
      for y2 in range(1,y1+1):
        test = sum_num[x1][y1] - sum_num[x1][y2-1] - sum_num[x2-1][y1] + sum_num[x2-1][y2-1]

3. 지나온 모든 부분행렬의 합 중, max를 출력하면 된다.

 

2. 내가 작성한 코드

import sys

input = sys.stdin.readline

n,m = map(int, input().rstrip().split())

num = [[0]  * (m+1)]

for i in range(n):
  num_row = [0] + list(map(int, input().rstrip().split()))
  num.append(num_row)

sum_num = [[0]  * (m+1) for _ in range(n+1)]

max_num = -10000

for i in range(1,n+1):
  for j in range(1,m+1):
    sum_num[i][j] = sum_num[i-1][j] + sum_num[i][j-1] - sum_num[i-1][j-1] + num[i][j]

for x1 in range(1,n+1):
  for y1 in range(1,m+1):
    for x2 in range(1,x1+1):
      for y2 in range(1,y1+1):
        test = sum_num[x1][y1] - sum_num[x1][y2-1] - sum_num[x2-1][y1] + sum_num[x2-1][y2-1]
        max_num = max(max_num, test)

print(max_num)

 

 

아무리 봐도 로직의 개선이 필요할 것 같아서 구글링을 해보았고, 행과 열의 누적합을 달리해 값을 구하 방법을 찾았다.

 

https://velog.io/@boorook/Python-%EB%B0%B1%EC%A4%80-1749-%EC%A0%90%EC%88%98%EB%94%B0%EB%A8%B9%EA%B8%B0

[Python] 백준 1749 - 점수따먹기

 

이 분의 글을 참고해서 문제를 해결하면 시간복잡도를 반절로 줄일 수 있다.

 

 

 

다른 분들의 코드를 참고하는데 C++ 이 8ms 인 걸 보고 C++ 도 한 번 공부해보면 좋겠다는 생각을 해봤삼,,