Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- DP
- 정렬
- 이분 탐색
- 애드 혹
- 싸피
- 슬라이딩 윈도우
- 트리
- 맵
- DFS
- 정수론
- Python
- 투 포인터
- SSAFY
- 모던 JavaScript 튜토리얼
- 13164
- 세그먼트 트리
- boj
- 구현
- JavaScript
- 수학
- 문자열
- 2357
- 그래프
- 누적 합
- 브루트포스
- 에라토스테네스의 체
- BFS
- 그리디
- 해시 테이블
- 플로이드-워셜
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 22862 - 가장 긴 짝수 연속한 부분 수열 (large) (Python) 본문
아이디어
누적합으로 S에서 홀수 원소들을 최대 K번 삭제한 연속된 짝수 수열의 길이를 구한다.
풀이
22857번 가장 긴 짝수 연속한 부분 수열 (small)의 풀이 #2와 같다.
리스트 arr에는 홀수 원소로 구분된 짝수로 이루어진 수열의 길이를 누적합으로 저장한다.
for문에서 S의 각 원소가 홀수면 리스트 arr에 arr의 마지막 값을 다시 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다.
arr의 K 번째 원소까지는 앞의 홀수 원소들을 모두 제거할 수 있으므로 그 마지막 값을 결과값 res에 저장한다.
for문에서 K개의 홀수 원소를 제거한 짝수로 이루어진 수열 길이의 최댓값으로 res를 갱신해 나간다.
arr의 길이 M이 K보다 작다면 결과값 res에는 누적합의 최댓값이 저장되고, for문은 실행되지 않는다.
def solution():
N, K = map(int, input().split())
S = list(map(int, input().split()))
arr = [0]
for i in range(N):
if S[i]%2:
arr.append(arr[-1])
else:
arr[-1] += 1
res = arr[:K+1][-1]
M = len(arr)
for i in range(K+1, M):
if arr[i]-arr[i-(K+1)] > res:
res = arr[i]-arr[i-(K+1)]
print(res)
solution()
'알고리즘' 카테고리의 다른 글
[BOJ] 1275 - 커피숍2 (Python) (0) | 2023.02.22 |
---|---|
[BOJ] 1890 - 점프 (Python, JavaScript) (0) | 2023.02.22 |
[BOJ] 22857 - 가장 긴 짝수 연속한 부분 수열 (small) (Python, JavaScript) (0) | 2023.02.21 |
[BOJ] 1725 - 히스토그램 (Python) (0) | 2023.02.20 |
[BOJ] 2748 - 피보나치 수 2 (Python, JavaScript) (0) | 2023.02.20 |
Comments