[BOJ] 22857 - 가장 긴 짝수 연속한 부분 수열 (small) (Python, JavaScript)

 

 

아이디어

 

S의 홀수 원소로 구분된 연속된 짝수 수열의 길이를 구한 후 그 길이의 합의 최댓값을 찾는다.

 

 

풀이 #1 (Python)

 

리스트 arr의 초기값으로 0을 넣어두고 S의 각 원소가 홀수면 arr에 0을 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다.

따라서 arr에는 짝수로 이루어진 수열의 길이가 홀수 원소로 구분되어 저장되고,

연속된 arr 원소들의 합은 그 원소 수만큼 S에서 홀수 원소를 삭제한 짝수로 이루어진 수열의 길이와 같다.

 

arr을 복제해 리스트 dp에 저장하고, for문에서 앞의 홀수 원소를 반복 횟수만큼 삭제한 수열의 길이로 dp를 갱신해 나간다.

같은 for문 내에서 구한 값이 현재 결과에 영향을 미치지 않도록 dp의 원소들을 역순으로 갱신한다.

 

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(0)
        else:
            arr[-1] += 1
    dp = arr[:]
    M = len(dp)
    for _ in range(K):
        for i in range(M-1, 0, -1):
            dp[i] = arr[i]+dp[i-1]
    print(max(dp))

solution()

 

 

 

풀이 #2 (Python)

 

풀이 #1에서 연속된 arr 원소들의 합을 동적 계획법이 아닌 누적합으로 구한다.

 

S의 각 원소가 홀수면 arr에 0이 아닌 arr의 마지막 값을 다시 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다.

arr에는 홀수 원소로 구분된 짝수로 이루어진 수열의 길이가 누적된 합이 저장된다.

 

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()

 

 

 

풀이 #3 (JavaScript)

 

풀이 #2와 마찬가지 방식으로 동작하며, arr의 최대 K 번째 값의 인덱스를 구하기 위해 slice 메서드를 사용한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [N, K] = input[0].split(' ').map(Number);
const S = input[1].split(' ').map(Number);
let arr = [0];
for (let i=0; i<N; i++) {
    if (S[i]%2) arr.push(arr[arr.length-1])
    else arr[arr.length-1] += 1
}
let res = arr[arr.slice(0, K+1).length-1];
const M = arr.length;
for (let i=K+1; i<M; i++) {
    if (arr[i]-arr[i-(K+1)] > res) res = arr[i]-arr[i-(K+1)];
}
console.log(res);