1806번 - 부분합 / gold 4 / 투 포인터

- 시간 초과

"""
1806번 - 부분합 / gold 4
"""
import sys

input = sys.stdin.readline

n, s = map(int, input().split())
seq = list(map(int, input().split()))
# 누적 합으로 바꾸기
for i in range(1, n):
    seq[i] = seq[i - 1] + seq[i]


sum_len = 1
while sum_len <= n:
    flag = 0
    for i in range(sum_len - 1, n):
        if i == sum_len - 1:
            res = seq[i]
            if res >= s:
                flag = 1
                break
        else:
            j = i - sum_len
            res = seq[i] - seq[j]
            if res >= s:
                flag = 1
                break
    if flag == 1:
        break
    sum_len += 1

print(sum_len)

 

- 정답

"""
1806번 - 부분합 / gold 4 / 투 포인터
"""
import sys

input = sys.stdin.readline
INF = int(1e9)

n, s = map(int, input().split())
seq = list(map(int, input().split()))
# 리스트 앞에 0을 추가 / start 포인터가 처음에 가리키는 값
seq = [0] + seq
# 누적 합으로 바꾸기
for i in range(1, n + 1):
    seq[i] = seq[i - 1] + seq[i]

# seq 누적 합 리스트의 마지막 인덱스는 모든 값들을 합한 것
# 만일 모든 값들을 합한 것보다 s가 크면 바로 0 출력
if seq[-1] < s:
    print(0)
else:
    # 투 포인터 알고리즘 시작
    start = 0
    end = 1
    min_len = INF

    while start != n:
        # seq[end] - seq[start] 값이 s보다 크거나 같을 때
        # start++ 시키기
        if seq[end] - seq[start] >= s:
            if end - start < min_len:
                min_len = end - start
            start += 1
        # seq[end] - seq[start] 값이 s보다 작을 때
        # 보통 end++ 시키기 (end가 인덱스 끝까지 갔으면, start++)
        else:
            if end != n:
                end += 1
            else:
                start += 1
    print(min_len)

 

- 첫 번째로 작성한 코드는 완전 탐색에 가까운 코드인듯.. ?

 

정답 코드 / 투 포인터 알고리즘

- 설명은 주석 처리로