[알고리즘/동적 계획법] 22857번 : 가장 긴 짝수 연속한 부분 수열(small) - python

링크 : https://www.acmicpc.net/problem/22857

22857번: 가장 긴 짝수 연속한 부분 수열 (small)

 

---

• 문제
• 소요시간: 45분 10초, 다른 분의 풀이 참고로 재도전

---

• 설계하기(접근방법) 

내 풀이 (pypy3에서만 통과)

1. n, k, s(리스트를 입력받는다)

 

2.알고리즘 해석

1) 입력받은 리스트를 짝수는 +1, 홀수는 -1로 바꾸어 준다

 

2) 처음 원소부터 반복문으로 검사한다

 

검사내용 : 만약 원소가 짝수라면[+1] cnt(짝수개수)에 1을 더해준다

만약 원소가 홀수라면[-1] check(삭제 가능한 홀수 개수) 에서 1을 빼준다

 

check가 0 아래로 떨어지거나, 체크하는 범위라 리스트를 벗어나면 while문을 탈출한다

총 cnt(연속 가능한 짝수 갯수)를 dp에 저장한다

 

3. max(dp)를 출력한다

 

-> 전부 순회로 인한 시간초과 발생

 

 

 

다른 블로거 풀이 참고 (python3도 통과)

 

전체적인 구상은 비슷하나, 투 포인터를 쓴다는 점이 달랐다

 

나는 전체를 순회하여 시간이 오래 걸린 반면에 다른 블로거 분은

check(가능한 홀수 개수)가 초과하면,

지금까지 검사한 사항들은 유지하고, 맨 앞의 포인터만 1칸 움직이고

맨 뒤의 포인터부터만 다시 검사한다.

 

내 것은 O(n^2)에 완전탐색인 반해, 다른 블로거의 코드는 실직적으로 O(n)에 가까운 시간이 걸릴 것이다.

 

즉 중복 검사할 부분이 있다면 맨 앞뒤의 포인터만 조금 조정하는 것만으로도 다음 순회의 검사결과를 얻을 수 있다.

 

 

 

---

• 코드(출력)
• 내 코드

import sys

input = sys.stdin.readline

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

dp = [0 for _ in range(n)]
check = k
cnt = 0

for i in range(n):
    if s[i] % 2 == 0:
        dp[i] = 1
    else:
        dp[i] = -1

for i in range(n):
    j = 0
    while (check >= 0 and i + j < n):
        if dp[i + j] == 1:
            cnt += 1
        else:
            check -= 1
        j += 1
    dp[i] = cnt
    cnt = 0
    check = k


print(max(dp))

• 다른 분의 코드 참고

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

cnt = 0
start, end = 0, 0
size, size_max = 0, 0
flag = 1

for start in range(n):
    while cnt <= k and flag:
        if s[end] % 2:
            if cnt == k:
                break
            cnt += 1
        size += 1
        if end == n - 1:
            flag = 0
            break
        end += 1
        
    if size_max < size - cnt:
        size_max = size - cnt
        
    if s[start] % 2:
        cnt -= 1
        
    size -= 1

print(size_max)

---

• 얻어갈 부분

1. 투 포인터를 자세히 다루어봐야겠다

2. 알고리즘을 짤 때 O(n^2)의 알고리즘 사용 시 시간이 초과할지 안할지 미리 구상해보자. 이 문제의 경우 주어지는 길이가 50000이니 약 2억 5천번의 계산이 이루어진다. 즉 시간을 초과할 가능성이 높기 때문에 다른 방법을 떠올렸어야 할 것이다