[백준/Python] 22862: 가장 긴 짝수 연속한 부분 수열
문제: 가장 긴 짝수 연속한 부분 수열
문제: 가장 긴 짝수 연속한 부분 수열

풀이
import sys
input = sys.stdin.readline
# N: 수열의 길이
N, K=map(int, input().split())
S = list(map(int,input().split()))
#max는 최대 수열길이
max = 0
'''
N까지의 수 중에서 K번 삭제한 후
만약 N//2 <= K
N=6, K=3 ,2,4,6
N=6, K=4 2 4 6 -> 답은 N//2
N=7, K=4 ,2,,4,,6,
N=8, K=4 ,2,,4,,6,8
N//2 > K
N = 10, k = 4
1,2,,4,,6,,8,,10 -> 답은 k+1
S가 정렬되어있지않을 수도 -> 근데 정렬은 상관없느듯
짝수 뭉탱이가 중간에 숨어있을 수 있음 -> 찾아야됨
홀수 K개 지울 수 있음 -> 투포인터로 홀수 찾으면서 K개 될때까지
두개의 포인터 안에 홀수가 K보다 작을때
end포인터 +1
두개의 포인터 안에 홀수가 K보다 클떄
st포인터 +1
두개의 포인터 안에 홀수의 수 = K일때
end 포인터, st +1
if end - st > max:
max = end-st
'''
#end랑 st는 투포인터
end = 0
st = 0
# print(N//2 if N//2<=K else K+1)
length=len(S)
odd = 0
#매번 odd를 세니깐 시간초과
# odd를 저장해두고,포인터 이동에따라 1씩 더하거나 빼기
while end < length:
# for i in S[st:end+1]:
# if i%2 == 1:
# odd +=1
#홀수라면 odd +=1
if S[end]%2 == 1:
odd +=1
# if odd < K:
# if end - st + 1 - odd > max:
# max = end-st+1 - odd
# end +=1
while odd > K:
if S[st] % 2 == 1:
odd-=1
st += 1
#odd <=K일때 max길이 검사
if end - st +1 - odd > max:
max = end-st+1 - odd
end+=1
# print(S)
print(max)
배울점
- 어렴풋이 알고는 있었는데, 당연히 while문 안에서 매번 수열 S를 슬라이싱해서 홀수개수를 세면 시간초과뜸 → 이럴경우에 정수로 개수를 센다음에 while 루프마다 정수 +-1씩 업데이트 해가면서 개수를 세는게 맞음 → 약간 DP table만들어서 이전 정보 활용하는 느낌 → 매번계산x
- odd = K일때 max길이 검사해야 하는것은 알았는데, odd<K에도 max길이 검사해야하는것을 놓쳤음 → 홀수 수는 K보다 크지만 않으면 상관없음.
Continue exploring
더 읽어보기
CTR을 예측할 수 있을리가 없잖아 무리무리!(무리가아니었다!?): nemotron persona
어떤 광고 배너가 잘될지는 결국 집행 비용을 써봐야 알 수 있었다. 배너를 많이 만들 수 있어도, 그중 무엇을 내보낼지 고르는 데는 여전히 돈이 들었다. 집행 전에 후보를 걸러낼 수 있을지 확인하려고 NVIDIA Nemotron Persona-Korea 데이터셋으...
카피 A/B 테스트와 밈으로 광고 성과를 끌어올리기
광고 배너를 자동으로 만들 수 있게 된 뒤에는 어떤 카피를 얹을지가 다음 과제였다. 성과가 높은 카피, 재밌는 카피에는 정해진 Ground Truth가 없었다. 여러 톤앤매너와 밈 RAG로 후보를 만들고 실제 광고 성과를 비교했다.
성과가 난 광고에서 다음 스토리를 찾는 위닝앵글 검색
초기 AX 제작은 좋아요 랭킹 순으로 스토리를 넓게 탐색하는 방식이었다. 이후에는 이미 성과가 난 광고에서 다음 후보를 찾는 경로를 만들었다. 다른 팀원이 만든 에이전트의 광고 성과 분석과 인사이트를 받아, 비슷한 소구점이나 이미지를 가진 새로운 스토리를 발굴하는...