[ BOJ /파이썬 ] 11660 구간 합

모두가 처음 접하면 같은 과정을 거치는 듯한 문제인 것 같다. 

2중 for문으로 생각했다가 아무리 생각해도 시간 초과인데.. 싶으면서 일단 해보고 역시나 시간초과가 나서 풀이를 찾아보는..?

 

'누적 합' 구현 방식을 이해하고 나면 또 금새 해결된다.

내가 약한 dp풀이가 섞여들어가서 나는 단번에 이해가 된 건 아니었는데 아래 링크 보고 확실히 이해할 수 있었다.

 

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Silver1-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-11660-%EA%B5%AC%EA%B0%84-%ED%95%A9

백준/ Silver1 문제 , 백준 파이썬 11660 , 구간 합

 

위 링크를 읽고 누적합알고리즘 자체랑 누적값 dp테이블 구하는 건 이해가 갔는데

 

그 테이블 이용해서 값 구할 때 왜 합산 값을 또 안 구하나 헷갈리는거 보니까 완전히 이해 못 한거였다.

 

아래 걸 읽고 더 깊게 이해가 됐는데

 

https://ji-musclecode.tistory.com/38

누적합(Prefix Sum / Cumulative Sum) 알고리즘

 

행 and 열 기준으로 그 때까지의 값이 구해진거라고 보면 된다. 그래서 해당 구간 끝값 자체만 빼면 되는 거였다. 

 

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
# 행, 열 각 첫번째 줄은 0으로 비워두기. board자체에서 누적합배열 리셋 위해서.
board = [[0]*(n+1)]+[[0]+list(map(int,input().split())) for _ in range(n)]

# 누적 합 배열 구하기
for i in range(1,n+1):
    for j in range(1,n+1):
        board[i][j] = board[i][j]+board[i-1][j]+board[i][j-1]-board[i-1][j-1]

# 구간 합 구하기
for _ in range(m):
    x1,y1,x2,y2 = map(int,input().split())
    print(board[x2][y2]-board[x1-1][y2]-board[x2][y1-1]+board[x1-1][y1-1])

 

 

프로그래머스에 있는 더 심화내용 풀어보며 익혀보면 좋을 것 같아 아래 문제도 함께 풀어봤다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=python3 

프로그래머스