백준 11659, 11660, 10986

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

11659번: 구간 합 구하기 4

<내풀이>

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

num = []
while n>0:
    num.append(n)
    n -=1
    
li=[]
for i in range(m):
    li.append((input('구간').split(' ')))

for i,j in li:
    print(sum(num[int(i)-1:int(j)]))

위의 코드는 주피터에서 적용해보면 알맞은 정답을 잘 도출은 하지만 0.5초안에 결과도출이 되지 않아 런타임 에러가 발생합니다. 책에서는 합을 구해야하는 횟수가 최대 100,000번이기 때문에 0.5초 안에 모든 구간 합 계산을 끝내기 위해서는 미리 숫자를 받자마자 합 배열을 생성하고 합 배열을 통해서 정답을 도출하는 방법을 사용했습니다.

import sys
input = sys.stdin.readline

suNo, quizNo = map(int, input().split())
numbers = list(map(int,input().split()))
prefix_sum = [0]
temp = 0

for i in numbers:
    temp = temp + i
    prefix_sum.append(temp)
    
for i in range(quizNo):
    s,e = map(int, input().split())
    print(prefix_sum[e]-prefix_sum[s-1])

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

11660번: 구간 합 구하기 5

위의 문제 역시 질의하는 횟수의 범위m이 최대 100,000번이기 때문에 매번 계산하는 것이 아니라 정답판을 만들어놓고 바로 답을 출력하는 형태로 문제를 풀어야합니다. 

합배열을 이용하면 정답판을 쉽게 만들 수 있습니다.

2차원 구간 합 배열 D[x][y] = D[x-1][y] + D[x][y-1] - D[x-1][y-1] + A[x][y] 로 정의할 수 있습니다.

완성된 합배열 D[i][j]

그렇다면 x1,y1, x2,y2구간이 질의로 정해졌을 때 구해야하는 답은

D[x2][y2] - D[x1-1][y2] + D[x2][y1-1] + D[x1-1][y1-1] 입니다. 구간을 표시해가면서 보면 이해가 훨씬 쉽습니다.

 

따라서 답은 아래 코드로 도출해볼 수 있습니다.

# input을 빠르게 받기 위해
import sys
n, m = map(int, input().split())
input = sys.stdin.readline

# 파이썬의 index 번호는 0번부터 시작하기 때문에 0으로 채워진 행,열을 한칸 더 만들어준다.
A = [[0] * (n+1)]
# A = [[0, 0, 0, 0... n+1 개]]
D = [[0] * (n+1) for i in range(n + 1)]
# D = [[0, 0, 0, 0... n+1 개],[0, 0, 0, 0... n+1 개],...n+1개]

for i in range(n):
	A_row = [0] + [int(x) for x in input().split()]
    A.append(A_row)
# A = [[0, 0, 0, 0... n+1 개], [0, input에서 받은 숫자들, , ,...],...]
# 결국 2차원 행열의 모양이 된다.

# 합 배열 만들기
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]

# m번 받는 구간을 좌표로 만들기
for i in range(m):
	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)

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

10986번: 나머지 합

<내풀이>

# 빠른 연산을 위해 import sys를 하고
# 추후 경우의 수를 계산하기 위해 math모듈의 comb를 import
import sys
input = sys.stdin.readline
from math import comb

# 주어진 숫자열은 A에 저장하고
# 구간합을 구하는 S배열을 생성한다. 
n, m = map(int, input().split())
A = list(map(int, input().split()))
S = [0]*(n+1)
for i in range(1,n+1):
    S[i] = S[i-1] + A[i-1]

# 구간합을 m 으로 나눈 후 나머지가 0이면 count해준다.
count = 0
for i in range(1,n+1):
    S[i] = S[i] % m
    if S[i] == 0:
        count += 1

# 나머지는 m보다 작을 것이기 때문에 C 리스트 생성 후
# 나머지 배열(S)에서 동일한 값이 있는지 검사 후 C 배열에 카운트 해준다
C = [0]*m
for i in range(m):
    C[i] = S[1:].count(i)

# 동일한 값이 겹치는 것이 있다면 경우의 수를 구해서 count에 더해준다
for i in range(m):
    if C[i] > 1:
        count += comb(C[i], 2)

print(count)

> 해당 문제는 for문을 아주 많이 써서 단순히 조합을 비교해보는 방법으로 접근하면 시간 초과가 걸리는 문제입니다. 따라서 문제집에서 알려주는  수학적인 접근 방법을 힌트로 받아서 코드를 직접 작성해보았습니다. 위에서 가장 중요한 포인트는 구간합에서 나머지가 같은 인수들은 서로 뺐을 때 나머지가 0이 된다는 것 입니다. 예를 들어, [1 , 2 , 1] 의 숫자 배열의 구간 합은 [ 1, 3, 4] 이고 각 수들을 3으로 나누었을 때 나머지는 [1, 0, 1] 입니다. 그리고 큰수에서 작은 수를 빼주는 기준으로 나머지가 같은 4에서 1을 빼주면 나머지가 사라지기 때문에 3으로 나누었을 때 딱 떨어지는 수가 됩니다. 즉, 세번째 구간합(= 1+ 2+ 1) 에서 첫번째 구간합(= 1)을 빼준 두번째와 세번째 연속된 수는 3으로 나누어 떨어지는 수 입니다.

 

해당 코드로 조금 더 빠르고 단순하게 코드를 짤 수 있었습니다.