TIL 코딩공장

백준 파이썬 공부 2025.10.25
2096번 내려가기 (골드 5)

1. 문제
N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 
내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 
그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 
바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 
이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 
빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 
숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 
점수는 원룡이가 위치한 곳의 수의 합이다.

2. 입력
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 
다음 N개의 줄에는 숫자가 세 개씩 주어진다. 
숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

3. 출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

4. 문제 풀이
다이나믹 프로그래밍 문제이다. 최소값과 최대값 모두를 구하기 위해 DP를 두 개 시행해야한다.

>>코드1. 메모리 초과

n = int(input())
score = [list(map(int, input().split())) for _ in range(n)]
    
DP1 = list([0] * (n+2) for _ in range(n+1))
DP2 = list([100001] * (n+2) for _ in range(n+1))
DP2[0] = [0] * (n+2)
    
for i in range(1, n+1):
    for j in range(1, n+1):
        DP1[i][j] = max(DP1[i-1][j-1], DP1[i-1][j], DP1[i-1][j+1]) + score[i-1][j-1]
        DP2[i][j] = min(DP2[i-1][j-1], DP2[i-1][j], DP2[i-1][j+1]) + score[i-1][j-1]

print(max(DP1[-1]), min(DP2[-1]))

문제 해결을 위해 각 자리에서의 최대값과 최소값을 저장하는 
(n+2) X (n+1) 리스트를 생성했으나 메모리 초과가 발생하였다.
이전 경로들의 최대값과 최소값은 저장할 필요가 없으니 일차원 리스트에 다시 최대값과 최소값을 저장해보자.

>> 정답코드

"""
2096번 내려가기
입력 : n (층수), score (위치의 점수)
출력 : max_score (최대 점수), min_score (최소 점수)
(이동 경로의 모든 점수의 합의 최댓값과 최솟값)
"""
n = int(input())

a, b, c = map(int, input().split())
max_dp = [a, b, c]
min_dp = [a, b, c]

for _ in range(n - 1):
    a, b, c = map(int, input().split())
    prev_max = max_dp[:]
    prev_min = min_dp[:]
    
    max_dp[0] = a + max(prev_max[0], prev_max[1])
    max_dp[1] = b + max(prev_max[0], prev_max[1], prev_max[2])
    max_dp[2] = c + max(prev_max[1], prev_max[2])

    min_dp[0] = a + min(prev_min[0], prev_min[1])
    min_dp[1] = b + min(prev_min[0], prev_min[1], prev_min[2])
    min_dp[2] = c + min(prev_min[1], prev_min[2])

print(max(max_dp), min(min_dp))

일차원 리스트에 매 층의 위치에서의 최소경로와 최대경로 값을 저장하여,
각각 길이 n의 일차원 리스트만 필요했다.

5. 문제 링크
https://www.acmicpc.net/problem/2096

백준 파이썬 공부 2025.10.23
9251번 LCS (골드 5)

1. 문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 
모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

2. 입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 
문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

3. 출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

4. 문제 풀이
다이나믹 프로그래밍을 bottom-up 방식으로 설계하여, 이차원 DP 리스트를 이용하여 문제를 해결한다.

DP의 초기값을 0으로 잡아놓고 문자열의 길이보다 1씩 길게하여 이차원 리스트를 생성한다.
DP[i][j] 에는 각각 첫번째 문자열 st1[0:i] 와 두번째 문자열 st2[0:j] 까지의 LCS 길이를 저장한다.
각각의 길이에 대한 점화식은
if (st1[i-1] == st2[j-1]) >> DP[i][j] = DP[i-1][j-1] +1
else >> DP[i][j] = max(DP[i][j-1], DP[i-1][j]) 

>>코드

"""
9251번 LCS
입력 : string (문자열 x 2)
출력 : 두 문자열의 LCS 길이
(공통된 부분 수열 중 가장 긴 부분수열의 길이)
"""
st1 = input()
st2 = input()

length1 = len(st1)
length2 = len(st2)

# DP[i][j] : st1[0:i]와 st2[0:j]까지의 LCS 길이
DP = list([0] * (length2 + 1) for _ in range(length1+1))

for i in range(1, length1 + 1):
    for j in range(1, length2 + 1):
        if st1[i-1] == st2[j-1]:
            DP[i][j] = DP[i-1][j-1] + 1
        else:
            DP[i][j] = max(DP[i-1][j], DP[i][j-1])
        
    
print(DP[-1][-1])

         

5. 문제 링크
https://www.acmicpc.net/problem/9251

백준 파이썬 공부 2025.10.15
12865번 평범한 배낭 (골드 5)

1. 문제
이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 
세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 
각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 
아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 
준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

2. 입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 
두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

3. 출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

4. 문제 풀이
다이나믹 프로그래밍 방식으로 풀이한다.
dp[]를 해당 무게로 가질 수 있는 최대의 가치로 놓고 코드를 작성한다.

>>코드

"""
12865번 평범한 배낭
입력 : n (물품의 수), k (버틸 수 있는 무게)
w (물건의 무게), v (물건의 가치)
출력 : 배낭에 넣을 수 있는 물건의 가치합의 최대값

w의 합이 k이하이면서 최대값을 갖는 조합 찾기
"""
n, k = map(int, input().split())
package = [list(map(int, input().split())) for _ in range(n)]

# dp[w] = 배낭의 무게 한도가 w일 때 얻을 수 있는 최대 가치
dp = [0] * (k + 1)

for weight, value in package:
    # 뒤에서부터 갱신해야 같은 물건을 중복해서 넣지 않음
    for w in range(k, weight - 1, -1):
        dp[w] = max(dp[w], dp[w - weight] + value)

print(dp[k])

5. 문제 링크
https://www.acmicpc.net/problem/12865

백준 파이썬 공부 2025.10.14
13549번 숨바꼭질 3 (골드 5)

1. 문제
수빈이는 동생과 숨바꼭질을 하고 있다. 
수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 
수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 
순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 
수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

2. 입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

3. 출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

4. 문제 풀이
숨바꼭질 2번 이후의 문제이지만, 숨바꼭질 2번보다 간단한 문제이다.
단순히 동생을 찾는 가장 빠른시간을 찾는 문제이며,
이동 방식은 -1, +1 , x2 인데 -1, +1은 1초가, x2는 0초가 걸리는 것을 유의하며
BFS 너비우선탐색을 이용하여 문제를 풀면 된다.

>>>코드

"""
13549번 숨바꼭질 3
입력 : n (수빈의 위치), k (동생의 위치)
출력 : 
    - 수빈이가 동생을 찾는 가장 빠른 시간
"""
from collections import deque

n, k = map(int, input().split())

queue = deque()
queue.append(n)

visited = [-1] * (100001)
visited[n] = 0
while queue:
    now = queue.popleft()
    
    nextloc = [now-1, now+1, now*2]
    for loc in nextloc:
        if 0 <= loc < 100001:
            if visited[loc] == -1 or visited[loc] > visited[now] + 1:
                if loc == now*2:
                    visited[loc] = visited[now]
                else:
                    visited[loc] = visited[now] + 1
                queue.append(loc)

print(visited[k])

5. 문제 링크
https://www.acmicpc.net/problem/13549

백준 파이썬 공부 2025.10.13
12851번 숨바꼭질 2 (골드 4)

1. 문제
수빈이는 동생과 숨바꼭질을 하고 있다. 
수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 
수빈이는 걷거나 순간이동을 할 수 있다. 
만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 
순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 
수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 
그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

2. 입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. 
N과 K는 정수이다.

3. 출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

4. 문제 풀이
BFS를 이용하면서 최소시간과 해당 루트의 개수를 갱신하는 문제이다.
이동할 수 있는 방법은 3가지 -1, +1, x2 인데,
이동한 곳이 0 <= location < 100001 범위에 해당하면서
해당 위치에 이동한 적이 없거나, 이동하는 시간이 더 적거나 같을때, queue를 push해준다.

그리고 현재 location이 k인 경우,
이전에 이동한 경우의 이동시간과 현재 이동시간이 같으면 cnt++,
이전에 이동한 경우의 이동시간이 현재 이동시간보다 크면 cnt = 1부터 다시 시작

>>>코드

"""
12851번 숨바꼭질 2
입력 : n (수빈의 위치), k (동생의 위치)
출력 : 
    - 수빈이가 동생을 찾는 가장 빠른 시간
    - 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수
"""
from collections import deque

n, k = map(int, input().split())

queue = deque()
queue.append(n)

cnt, min_time = 0, 100001
visited = [-1] * (100001)
visited[n] = 0
while queue:
    now = queue.popleft()
    
    if now == k:
        if visited[now] == min_time:
            cnt += 1
        elif visited[now] < min_time:
            cnt = 1
            min_time = visited[now]
    
    nextloc = [now-1, now+1, now*2]
    for loc in nextloc:
        if 0 <= loc < 100001:
            if visited[loc] == -1 or visited[loc] >= visited[now] + 1:
                visited[loc] = visited[now] + 1
                queue.append(loc)

print(visited[k])
print(cnt)

5. 문제 링크
https://www.acmicpc.net/problem/12851

백준 파이썬 공부 2025.10.12
1916번 최소비용 구하기 (골드 5)

1. 문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 
우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 
A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 
도시의 번호는 1부터 N까지이다.

2. 입력
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 
둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 
그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 
먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 
그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 
버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 
출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

3. 출력
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

4. 문제 풀이
최소 비용 루트를 찾는 문제이다.
BFS와 DP를 이용하여 문제를 풀어보려고 했으나 메모리 초과가 발생하였다.

>>>메모리 초과

"""
1916번 최소비용 구하기
입력 : n (도시 수), n (버스 수), bus (버스 비용)
s, e (시작점, 도착지)
출력 : 목적지로 가는 최소 비용
"""
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
bus = [[] for _ in range(n+1)]

for _ in range(m):
    depart, arrive, fee = map(int, input().split())
    bus[depart].append((arrive, fee))
    
s, e = map(int, input().split())

def BFS():
    queue = deque()
    queue.append((s, 0))
    
    DP = [0] * (n+1)
    while queue:
        city, cost = queue.popleft()
        
        if city == e:
            if DP[city] == 0:
                DP[city] = cost
            elif DP[city] > cost:
                DP[city] = cost
        
        else:
            for arrive, fee in bus[city]:
                queue.append((arrive, cost+fee))
    
    return DP[e]
    
print(BFS())

코드를 돌려 보았을때 결과는 동일하게 나오지만,
메모리 오류가 나온다. 메모리 오류의 원인은 너무 많은 queue의 생성으로 예상되어,
queue가 삽입되는 조건을 조금 더 엄격하게 제한하였다.

- 해당 도시에서 출발하는 경우에, 
이미 기록된 비용보다 popleft된 비용이 높으면 queue를 추가하지 않고 다음 queue로 넘어갔으며
- queue를 삽입할 때, 해당 도착지에 도달할 비용이 기록된 비용보다 작을 경우에만 추가하였다

>>> 정답 코드

"""
1916번 최소비용 구하기
입력 : n (도시 수), n (버스 수), bus (버스 비용)
s, e (시작점, 도착지)
출력 : 목적지로 가는 최소 비용
"""
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
bus = [[] for _ in range(n+1)]

for _ in range(m):
    depart, arrive, fee = map(int, input().split())
    bus[depart].append([arrive, fee])
    
s, e = map(int, input().split())

def BFS():
    queue = deque()
    queue.append((s, 0))
    
    DP = [1e9] * (n+1)
    while queue:
        city, cost = queue.popleft()
        if DP[city] < cost:
            continue
        
        for arrive, fee in bus[city]:
            if DP[arrive] > cost + fee:
                DP[arrive] = cost + fee
                queue.append([arrive, cost+fee])
    
    return DP[e]
    
print(BFS())

5. 문제 링크
https://www.acmicpc.net/problem/1916

백준 파이썬 공부 2025.10.11
9465번 스티커 (실버 1)

1.문제
상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 
스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 
상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 
스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 
즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 
점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 
먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 
상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 
즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 
가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

2. 입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 
각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 
다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 
연속하는 두 정수 사이에는 빈 칸이 하나 있다. 
점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

3. 출력
각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

4. 문제 풀이
다이나믹 프로그래밍을 이용하는 문제이다.
2차원 리스트에서 이동가능한 경우의 수를 입체적으로 고려해야한다.
되도록이면, 그림을 그려보거나, 숫자를 써보면서 가능한 이동방식을 확인하는 것이 필요하다.

단순이 생각하면 지그재그로 전부 합한 것중에 더 큰걸 고르면 될 것 같지만,
각 스티커마다의 비중이 다르기 때문에 지그재그가 아니라, 
한칸 건너뛴 경우가 최종 점수가 더 큰 경우가 발생한다.

따라서 최대 값을 고려할 때, 위와 같은 일반 지그재그와 뛰어넘기 중 큰 경우로 계산을 해야한다.
현재 행이 i,  현재 열이 j이라고 할 경우 i가 아닌 행의 j-1 열과 j-2의 부분 중 더 큰 경우와 
현재 위치의 스티커 점수를 더해야한다.
- DP[0][i+1] = max(DP[1][i-1], DP[1][i]) + sticker[0][i]
- DP[1][i+1] = max(DP[0][i-1], DP[0][i]) + sticker[1][i]

>>>코드

"""
9465번 스티커
입력 : T (테스트케이스 수), n (열의 크기), sticker (스티커 점수)
출력 : 최대 스티커 사용 점수

다이나믹 프로그래밍 이용
현재 위치로 도달 가능한 2곳 : 다른 행의 j-1, j-2
첫번째 행의 위치에 따라 두번째 행의 스티커는 자동 선택
"""
import sys
input = sys.stdin.readline

for i in range(int(input())):
    n = int(input())
    sticker = [list(map(int, input().split())) for _ in range(2)]
    
    DP = [[0] * (n+1) for _ in range(2)]
    DP[0][1], DP[1][1] = sticker[0][0], sticker[1][0]
    
    for i in range(1, n):
        DP[0][i+1] = max(DP[1][i-1], DP[1][i]) + sticker[0][i]
        DP[1][i+1] = max(DP[0][i-1], DP[0][i]) + sticker[1][i]
    
    print(max(map(max, DP)))

5. 문제 링크
https://www.acmicpc.net/problem/9465

백준 파이썬 공부 2025.10.10
11660번 구간 합 구하기 5 (실버 1)

1. 문제
N×N개의 수가 N×N 크기의 표에 채워져 있다. 
(x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 
둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 
다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 
표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

3. 출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

4. 문제 풀이
동적 프로그래밍을 이용하여 풀이가 가능한 문제이다.
동적 프로그래밍으로 (1,1)에서 (x,y) 해당 값 까지의 직사각형 범위 합을 다른 곳에 저장해놓고,
구간합은 해당 구간합들의 차로 계산한다.

<구간 합>
# 해당 구간 합 = 위쪽 직사각형 + 왼쪽(아래) 직사각형 - 왼쪽(위) 직사각형 + 해당 부분 값
psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + sheet[i][j]

<최종 계산식>
해당 범위 전체 구간 합 - 왼쪽 직사각형 구간합 - 위쪽 직사각형 구간합 + 겹치는 부분 구간합
psum[x2][y2] - psum[x1-1][y2] - psum[x2][y1-1] + psum[x1-1][y1-1]

주의할 점
- 구간 합이 x1, y1 부터 x2, y2까지의 값을 모두 더하는 것이 아니라,
x1, y1을 왼쪽 위, x2, y2를 오른쪽 아래 꼭짓점으로 놓는 정사각형 범위의 합을 말하는 것이다.
(필자는 그냥 x1, y1부터 x2, y2의 값을 모두 더한 것인줄 알고 뻘 짓을 했다)

>>>코드

"""
11660번 구간 합 구하기 5
입력 : n (표의 크기), m (합을 구하는 횟수)
       sheet (표), section (구간)
출력 : 구간 합 출력
"""
import sys
input = sys.stdin.readline

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

# 2차원 누적합 배열 (1-indexed)
psum = [[0] * (n+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + sheet[i-1][j-1]

for x1, y1, x2, y2 in section:
    res = psum[x2][y2] - psum[x1-1][y2] - psum[x2][y1-1] + psum[x1-1][y1-1]
    print(res)

5. 문제 링크
https://www.acmicpc.net/problem/11660