ALGORITHM/SOLVE

[누적합] 누적합 죠패기 (백준 11659, 2559, 11660)

Jungry_ 2025. 5. 6. 22:00
반응형

https://www.acmicpc.net/step/48

 

누적합 죠패보겠음

 

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

 

11659 구간 합 구하기 4

import sys
input = sys.stdin.readline
data_no , quiz_no = map(int, input().split())
numbers = list(map(int, input().split()))

sum_list = [0]
sum = 0
# 누적합 구하기
for i in numbers:
    sum += i
    sum_list.append(sum)

# 입력 받은거 구하기
for j in range(quiz_no):
    start, end = map(int, input().split())
    print(sum_list[end] - sum_list[start-1])

 

누적합의 포인트는 누적합을 가진 배열을 만드는 것 !!!!

5 4 3 2 1

 

라는 배열이 있으면

[0,5,9,12,14,15]  이렇게 누적된 합을 가진 배열을 미리 만들어 놓고 

 

만약 1번 ~ 3번 까지의 합을 하면 누적합 의 3번 인덱스 - 누적합의 (1-1) 인덱스 를 하면 된다 12 - 0 = 12

2 ~ 4 라면 4번 인덱스 - (2-1) 인덱스 = 14 - 5 = 9

 

이렇게 하면 해결띠

 

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

 

2559 수열

import sys

input = sys.stdin.readline

N,K = map(int,input().split())
numbers = list(map(int, input().split()))

list_num = [0]
sum = 0
now_max = -9999999

# 누적합 만들기
for i in numbers:
    sum += i
    list_num.append(sum)

# max 값 구하기
for i in range(N-K+1):
    now = list_num[i+K] - list_num[i]
    now_max = max(now_max, now)

print(now_max)

 

동일하게 누적합을 가진 배열을 만든다

 

max 값을 구해야하는데 여기서는

 

1일 ~ 2일 = 누적합배열[2] - 누적합배열[2-2 (0)]

2일 ~ 3일 = 누적합배열[3] - 누적합배열[3-2 (1)] 이렇게 해주면 된다

 

 

만약 1일 ~5일 (K가 5인 경우) = 누적합배열[5] - 누적합배열[5-5] = -12 - 0 = 12

K 만큼 빼주면 된다

 

위에서는 배열이 0부터 시작하니까 i+K 로 하는 식으로 바꿈 !

 

값 범위는 N-K+1 인것을 잊지말자 !! 

 

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

11660 구간 합 구하기 5

import sys
input = sys.stdin.readline

n, q_num = map(int, input().split())
A = [[0] * (n+1)]
D = [[0] * (n+1) for _ in range(n+1)]

for i in range(n):
    A_row = [0] + list(map(int, input().split()))
    # A_row = [0] + [int(x) for x in input().split()]
    A.append(A_row)


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

# 합 배열로 질의 답변
for _ in range(q_num):
    x1,y1,x2,y2 = map(int, input().split())

    result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
    print(result)

 

이것도 합배열 구하는 방법이 중요한데

좌측꺼 + 위에꺼 - 좌측위 + 자기자신  하면 누적합을 구할 수 있다

 

합 배열을 구했다면 정해진 범위걸 빼야한다

그림으로 좀 설명했는데

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

2 2 3 4

이걸 예시로 들면 합 배열에서 (2,2) ~ (3,4) 까지의 범위는 보라색 네모 부분이다

맨 처음부터 (3,4) 까지의 합은 42 인건데 여기서 저 보라색 네모에 해당하지 않는 빨간 네모부분을 빼야한다

그래서 합 부분인 6, 10 을 빼고 1의 경우에는 6에도 포함되고 10에도 포함되니까 더해줌 ! (두번뺸거라)

 

 

어려워서 데굴데굴 

반응형