[알고리즘][Python] 백준(BOJ) 11660 구간 합 구하기 5_파이썬

 

11660 구간 합 구하기 5    https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍, 누적 합

 

 

 

 

 

 

 

풀이

<내용>

• 표를 입력받아 table에 저장한다.
• 완전 탐색을 하면 시간 초과가 뜨기 때문에 dp를 이용해서 해결해야 한다.
• table의 (x, y) 즉, x행 y열은 1행 1열부터 x행 y열까지의 합으로 채워지도록 for문을 통해 구현한다.
  • 행의 누적 합을 먼저 구한다.
  • 열의 누적 합을 더해준다.
• x1, y1, x2, y2가 주어질 때 (x1, y1)부터 (x2, y2)까지의 합을 구하는 규칙 및 예외를 찾고 구현한다.
  • x1과 y1이 1일 때 예외가 발생한다.

 

 

 

 

<코드>

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(n)]

for k in range(2):
    for i in range(n):
        if k == 1 and i == 0:
            continue
        for j in range(n):
            if k == 0:
                if j == 0:
                    continue
                table[i][j] += table[i][j-1]
            else:
                table[i][j] += table[i-1][j]

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == 1 and y1 == 1:
        print(table[x2-1][y2-1])
    elif x1 == 1:
        print(table[x2-1][y2-1] - table[x2-1][y1-2])
    elif y1 == 1:
        print(table[x2-1][y2-1] - table[x1-2][y2-1])
    else:
        print(table[x2-1][y2-1] - table[x2-1][y1-2] - table[x1-2][y2-1] + table[x1-2][y1-2])

 

+) 구간 합 구하기 4부터 해결하면 구간 합 구하기 5를 풀기 쉽다.

2020/09/07 - [Algorithm/백준 알고리즘] - [알고리즘][Python] 백준(BOJ) 11659 구간 합 구하기 4_파이썬

[알고리즘][Python] 백준(BOJ) 11659 구간 합 구하기 4_파이썬

 

 

 

 

 

 

 

 

 

 

 

시도 ==> 매번 합을 구하면 시간 초과

<내용>

• 매번 for문을 돌면서 구간 합을 해주는 방법이다.

 

 

<코드>

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(n)]

def solve(x1, x2, y1, y2, table):
    res = 0
    for i in range(x1-1, x2):
        res += sum(table[i][y1-1:y2])
    return res

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    print(solve(x1, x2, y1, y2, table))