[백준/python] 누적 합 전체 풀이(18단계)

 

목차

 

구간 합 구하기 4(#11659)

• Problem

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

  

• Solution

누적합을 이용한 풀이

        
import sys

input = sys.stdin.readline
n ,m = map(int,input().split())
a = [0]+list(map(int,input().split()))

for l in range(2,n+1):
    a[l]+=a[l-1]
res =[]
for o in range(m):
    i ,j = map(int,input().split())
    res.append(a[j]-a[i-1])

print(*res,sep='\n')

            

 

이 문제는 input이 아닌 readline을 사용하여야지 시간초과를 피할 수 있다. 처음에는 동적 계획법을 이용하여 2차원 배열을 만들어서 i부터 j까지의 수열합은 cumsum[i][j]안에 저장을 하여 문제를 해결하려고 하였지만 메모리 초과가 떴다. 그렇다면 굳이 전부 저장을 하지 않고 1차원 리스트로 매 입력마다 n번째의 칸에 처음부터 n 번째까지의 합을 저장하고 각 항목별로의 빼기를 이용하여 계산하고자 하였다.

---

 

 

 

수열(#2559)

• Problem

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,  3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 아래와 같다. 이때, 온도의 합이 가장 큰 값은 21이다.  또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,  이때, 온도의 합이 가장 큰 값은 31이다. 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오. 

 

• Hint

매번 온도를 다시 구하는 방법말고도 다른 방법을 생각해본다.

 

• Solution

누적합을 이용한 풀이

        
import sys

input = sys.stdin.readline

n ,k = map(int,input().split())
a = list(map(int,input().split()))
res=[0]*(n-k+1)

res[0]=sum(a[0:k])

for l in range(1,n+1-k):
    res[l]=res[l-1]-a[l-1]+a[l+k-1]

print(max(res))
            

 

시간초과가 뜨면 계산을 줄일 방법을 생각하여보자

---

 

 

 

인간-컴퓨터 상호작용(#16139)

• Problem

승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다.  '문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.' 승재를 도와 특정 문자열 $S$, 특정 알파벳 $\alpha$와 문자열의 구간 $[l,r]$이 주어지면 $S$의 $l$번째 문자부터 $r$번째 문자 사이에 $\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 $0$번째부터 세며, $l$번째와 $r$번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 $q$번 할 것이다.

 

• Solution

누적합을 이용한 풀이

        
import sys
input = sys.stdin.readline

cs = [[0]*26]
alist = input().rstrip()

for l in alist:
    addlist = cs[-1][:]
    a = ord(l)-97
    addlist[a]+=1
    print(cs)
    cs.append(addlist)

n = int(input())

for i in range(n):
    w,s,e = input().rstrip().split()
    w = ord(w)-97
    s = int(s)
    e = int(e)
    res = cs[e+1][w]-cs[s][w]

    print(res)
            

 

별도로 포스팅하였음.

---

 

 

나머지 합(#10986)

• Problem

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

 

• Hint

나머지가 0 이 되기 위해서는 mn+a 꼴로 나타내어서 a가 같은 값이 되는 쌍이 몇개나오는지 계산을 하면 된다.

 

• Solution

누적합을 이용한 풀이

        
import sys

n, m = input().split()
a = [0]+list(map(int,sys.stdin.readline().split()))
cs=[0]*int(m)
for i in range(1,len(a)):
    a[i]=(a[i]+a[i-1])%int(m)
    cs[a[i]]+=1
cnt=cs[0]
for j in cs:
    cnt+=int(j*(j-1)/2)

print(cnt)

            

따로 포스팅 예정

---

 

 

구간 합 구하기 5(#11660)

• Problem

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이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

 

• Hint

1차원 적인 방향으로만 누적합을 사용하려고 생각하는 것을 바꾸어보자

 

• Solution

누적합을 이용한 풀이

 

        
import sys
input = sys.stdin.readline

n,m = map(int, input().rstrip().split())
cs=[[0]*(n+1) for r in range(n+1)]
for i in range(1,n+1):
    td = 1
    for j in map(int, input().rstrip().split()):
        cs[i][td]=cs[i][td-1]+cs[i-1][td]-cs[i-1][td-1]+j
        td+=1
res=0
for k in range(m):
    xf,yf,xe,ye=map(int,input().rstrip().split())
    res=cs[xe][ye]-cs[xe][yf-1]-cs[xf-1][ye]+cs[xf-1][yf-1]
    print(res)
            

 

for문이 반복되는 횟수에 그에 따라서 증가하는 시간복잡도 등을 중점적으로 파악해서 풀이 전략을 세우는 것이 좋다.

 

내가 세운 방법도 마음으로는 너무 복잡한것이 아닌가 싶었지만 다른 방법들과 비교하여 시간 복잡도를 계산하였을때 - 처음 세운방법 이전 문제처럼 누적합을 가로로만 진행한다. 이후에 처음 x와 나중 x값 sum[xf:xe][n+1]을 이용하여 계산을 하는 방식으로 사잇 블럭값(문제에서 구하라고 한 값)을 구해준다.

- 제출한 방법 설정한 값의 2사분면에 존재하는 모든 값들의 합을 저장하여 누적합을 계산하여준다.

 

따라서 이 방법대로 풀이를 하기 위해서는 위쪽의 방식대로 누적합을 진행 한 후에 사잇 블럭값을 구하기 위해 최우측하단의 값에 좌측 여백과 윗쪽 여백을 빼준후에 빼준 두 범위의 공통 범위에 대한 값을 더해주는 방식으로 계산을 해준다.

 

하지만 n값이 증가할 수록 답으로 제출한 알고리즘 보다 복잡도가 증가하게된다.

 

따라서 적은 숫자일때는 위 알고리즘이 우수하지만 값이 커져도 해를 구하기 위한 for문 탐색에 있어서 동일한 시간복잡도를 갖는다.

---

 

 

 

체스판 다시 칠하기 2(#25682)

• Problem

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

• Hint

pypy로 통과를 했다면 B가 먼저 나오는 경우 W가 먼저 나오는 경우 둘다를 계산을 해야만 하는지 생각해보자

 

• Solution

누적 합을 이용한 풀이

 

        
import sys
input = sys.stdin.readline

n,m,k = list(map(int,input().rstrip().split()))

b=[[0]*(m+1) for j in range(n+1)]
w=[[0]*(m+1) for j in range(n+1)]

for i in range(1,n+1):
    a= list(input().rstrip())
    for j in range(1,m+1):
        w[i][j]=w[i-1][j]+w[i][j-1]-w[i-1][j-1]
        b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
        if (j+i)%2==0:
            if a[j-1]=="B":
                w[i][j]+=1
            else:
                b[i][j]+=1
        else:
            if a[j-1]=="W":
                w[i][j]+=1
            else:
                b[i][j]+=1
minres = 4000000
for r in range(k,n+1):
    for s in range(k,m+1):
        minres = min(minres,w[r][s]-w[r-k][s]-w[r][s-k]+w[r-k][s-k],b[r][s]-b[r-k][s]-b[r][s-k]+b[r-k][s-k])
        
print(minres)
            

 

따로 포스팅하였음