9. 20159 동작 그만. 밑장 빼기냐? 9.1. 문제유형 누적합 9.2. 풀이과정 밑장 빼기는 나, 상대방에게 주는 경우와 하지 않는 경우가 있다. 내 차례에 밑장을 빼는 경우, 상대방 차례에 밑장을 빼는 경우를 고려한다. 예를 들어 1,2,3,4,5,6,7,8,9,10을 대상으로 계산 후 점화식을 도출해 볼 수 있다. 점화식을 도출할 때, 미리 짝수/홀수 인덱스에 대한 누적합을 계산한 후 점화식에 활용한다. 9.3. 소스코드 n = int(input()) card = list(map(int, input().split())) mid = n//2 odd, even = card[0::2], card[1::2] answer = sum(odd) for i in range(1, mid): odd[i] += o..

7. 14465 소가 길을 건너간 이유 5 7.1. 문제유형 누적합, 슬라이딩 윈도우 7.2. 풀이과정 정상 신호등의 누적합 개수를 구한다. k개의 연속된 신호등을 구할 것이므로 i ~ i+k-1까지의 값을 계산한다. 2번 결과의 최대값을 구한다. k - 최대값 출력 7.3. 소스코드 from copy import deepcopy n,k,b = map(int, input().split()) sign=[1]*(n+1) psum=[0]*(n+1) sign[0]=0 for _ in range(b): broken = int(input()) sign[broken]=0 psum = deepcopy(sign) for i in range(1, n+1): psum[i] += psum[i-1] answer=0 for i ..

5. 21758 꿀 따기 5.1. 문제유형 누적합 5.2. 풀이과정 누적합을 구한 후 꿀통의 위치를 기준으로 3가지 경우에 대해 각 10만번 연산을 수행하였다. 첫 번째는 꿀통이 오른쪽에 있는 경우 벌 한 마리는 가장 왼쪽에 위치 두 번째는 꿀통이 왼쪽에 있는 경우 벌 한마리는 가장 오른쪽에 위치 세 번째는 꿀통이 중간에 있는 경우 이 경우는 양 끝에 벌들이 위치한다. 누적합만 계산해 놓으면 2,3,4를 loop를 돌며 계산할 수 있으므로 O(N)에 해결할 수 있다. 5.3. 소스코드 from copy import deepcopy n=int(input()) h=list(map(int, input().split())) s = deepcopy(h) answer=0 for i in range(1, n): s[..

3. 11660 구간 합 구하기 5 3.1. 문제유형 누적합 3.2. 풀이과정 매 번 2중 for문을 계산할 시 시간초과가 발생할 것이다. 따라서 미리 누적합을 계산해 놓고, 구간별로 뽑아 리턴한다. 이 때, col 인덱스번호가 0이라면 종료값의 누적합을 덧셈한다. 시작 인덱스가 0이 아니라면 종료값 - 시작값을 덧셈한다. python 시간 초과 발생 -> pypy3로 통과 3.3. 소스코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) nums = [list(map(int, input().split())) for _ in range(n)] for i in range(n): for j in range(1, n): nums[i..

1. 20438 출석체크 1.1. 문제유형 누적합 원소별 합계를 구한 후 S[i] - S[i-1]을 활용해 문제를 풀어나간다. 1.2. 해결과정 전체 학생 수만큼 배열을 선언한다. 조는 학생을 체크한다. 출석 번호를 체크한다. 0번째부터 n+3까지 출석한 학생들의 누적합을 구한다. 구간 학생 수 - (누적합[구간 마지막값] - 누적합[구간 시작값]) 1.3. 소스코드 import sys input = sys.stdin.readline n,k,q,m = map(int, input().split()) sleep = [0]*(n+3) check = [0]*(n+3) for i in map(int, input().split()): sleep[i] = 1 for i in map(int, input().split(..