글 읽기 - 투포인터 질문입니다

mung5596 1년 전 0

문제는 맞혔지만 궁금해서 물어봅니다

이런 문제에서 만약 연속합이 n과 같을때 left를 올리든 right를 올리든 상관이 없나요?

n = int(input())

primes = [False, False] + [True] * (n-1)
lst = [0]
for i in range(2, n+1):
    if primes[i]:
        lst.append(lst[-1] + i)

        j = 2
        while i*j <= n:
            primes[i*j] = False
            j += 1

left, right = 0, 1
cnt = 0

while right < len(lst):
    cur_sum = lst[right] - lst[left]
    if cur_sum < n:
        right += 1
    elif cur_sum > n:
        left += 1
    else:
        cnt += 1
        left += 1


print(cnt)

nahwasa 1년 전 1

넵. left를 올려도 상관 없습니다. 심지어 둘다 같이 올려도 상관 없습니다. 어차피 0이 존재하지 않으므로, 만약 left=a, right=b에서 N을 만났따면, left=a이면서 right가 다른 값일 경우에도 답이 될 수 없고, right=b인 상태에서 left가 다른 값인 경우도 답이 될 수 없습니다. 따라서 둘 다 같이 올려도 상관없습니다.

다만 만약 0도 데이터에 포함된다면 모든 가능한 경우를 보기 위해서는 right만 올려야 합니다.

mung5596 1년 전 1

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

투포인터 질문입니다

mung5596 1년 전 0

nahwasa 1년 전 1

mung5596 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말