728x90
반응형
문제 바로가기
문제:
길이가 N인 수열 S가 있다. 수열 S는 1 이상인 정수로 이루어져 있다. 수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제를 할 수 있다. 예를 들어, 수열 S가 다음과 같이 구성되어 있다고 가정하자. 수열 S : 1 2 3 4 5 6 7 8 수열 S에서 4번째에 있는 4를 지운다고 하면 아래와 같다. 수열 S : 1 2 3 5 6 7 8 수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.
입력:
수열 S의 길이 N와 삭제할 수 있는 최대 횟수인 K가 공백으로 구분되어 주어진다. 두 번째 줄에는 수열 S를 구성하고 있는 N개의 수가 공백으로 구분되어 주어진다.
출력:
수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n,m = map(int,sys.stdin.readline().split(" "))
S = list(map(int,sys.stdin.readline().split(" ")))
#투 포인터 방법
start, end, count, res = 0, 0,0,0
result = -1e9
flag = 1
for i in range(n):
while count <= m and end <= n-1:
# 홀수 일때
if S[end] % 2:
# 홀수 의 숫자가 m개 이면
if count == m:
# 다 지운거니깐 브레이크
break
# 아직 m개가 아니면 홀수 갯수 증가
count += 1
# 홀수든 짝수든 길이 증가
res += 1
#end도 증가시켜 최장길이 만들어줌
end += 1
# 가장 긴 길이 최댓값 넣어주고
result = max(result,res-count)
# 이제 start 를 증가시켜주면서 비교해야함
# 홀수
if S[i] % 2:
# 홀수 갯수 늘린거 하나 빼주고
count -= 1
# 홀수든 짝수든 길이 증가해준거 하나 빼줌
res -= 1
print(result)
2. dp
n, k =list(map(int,input().split()))
s = [0] + list(map(int,input().split()))
dp = [[0]*(k+1) for _ in range(n+1)] # [처음부터i까지][삭제횟수]
for i in range(1,n+1):
for k in range(k+1):
# 짝수인 경우
if s[i] % 2 == 0:
# 삭제횟수는 안 늘어남, 수열길이는 늘어남
# 이전 수열 까지의 길이 + 1
dp[i][k] = dp[i-1][k] + 1
# 홀수인경우 k = 0 일 경우삭제 작업을 아직 한 번도 수행하지 않았다는 뜻 홀수인수를 삭제해도 현재까지의 연속 부분 수열에는 영향을 주지 않는다,
if k != 0 and s[i] % 2:
# 이전 상태에서 k-1번의 삭제 횟수를 사용한 경우의 값 >> s[i]를 삭제를 했다는 뜻
dp[i][k] = dp[i-1][k-1]
res = []
for i in dp:
res.append(i[k])
print(max(res))
이거 하는데 반나절 쓴거같다. 화이팅
반응형
댓글