백준 14246 K보다 큰 구간 파이썬 반례 1개 O

https://www.acmicpc.net/problem/14246

14246번: K보다 큰 구간

처음에는 시간 복잡도를 생각하지 않고 한번 작성해봤다. O(N^2) (결과는 당연히 시간 초과.)

 

n = int(input())
s = list(map(int,input().split()))
k = int(input())
sums = 0
re =0
for i in range(n):
    sums = s[i]
    for j in range(i+1,n):
        sums+=s[j]
        if sums>k:
            re+=(n-j)
            break
print(re)

위에 코드에서도 알 수 있듯이 구간 i~j에서 k를 넘으면 바로 종료시켜주고 더하는 것을 알 수 있다.

이것이 이 문제의 핵심 포인트이다. 

그래서 문제 분류에 맞게 두 포인터를 사용해 문제를 풀어봤다.

n = int(input())
s = list(map(int,input().split()))
k = int(input())
st,en=0,0
sums =0
re=0
while True:
    if en==n:#st~en에서 en 배열의 마지막까지 간 경우이다.
        if sums>k:#st~en가 k보다 크면 조건에 맞기에 re+=1해준다. 
            re+=1
            sums-=s[st]#st+1~en도 비교해주기 위해 해주는 작업이다.
            st+=1
        else:
            break
        continue#밑은  en이 배열의 마지막 부분이 아닐때기에 continue를 해줘 넘긴다.
    
    if sums <=k:
        sums+=s[en]#배열의 길이를 늘린다. 
        en+=1
    else:
        re+=n-en+1#한번 k를 넘었으면 그 뒤도 무조건 k를 넘기에 n-en+1를 더해준다 +1은 이전에 en+=1해줘서 해준거다. 
        sums-=s[st]#st를 늘려 새로운 기준을 만들고 비교해준다.
        st+=1
       
print(re)

5
1 2 3 4 5
5

답: 8

오답: 7 (else부분에서 sums-=s[en] , en+=1를 동시에 해주면 오답으로 7이 나온다. 문제에 나온 예제는 잘 나와서 놓치기 쉬움. )