[BOJ] 1806번 부분합 / 사용언어 : 파이썬(python)

※ 문제링크

1806번: 부분합

해당문제는 투 포인터를 활용하여 해결할 수 있는 문제였다. 주의해야할 점은 2가지 정도였는데, 

1. 부분합을 이루는 숫자들의 개수가 1개일 수도 있다.

2. sum함수를 사용하면 시간초과가 난다.(sum함수 호출없이 문제를 해결해야함)

처음에는 리스트형태로 변수를 선언하고 sum함수로 풀어보려다 시간초과가 나와서 코드를 변형하여 해결하였다. 즉, 조건을 충족하면서 문제를 해결하기 위해서는 결과값이 리스트형태가 아니라 한개의 변수형태로 해결해야하는 문제였으며,자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 각각 변수와 리스트에 저장해준다.

2. 2개의 포인터와 결과값 변수, 합을 구하는데 사용한 숫자갯수를 카운트할 변수, 숫자들의 합을 갱신한 변수를 선언해준다.

3. 두개의 포인터가 모두 N-1이 되면 반복문을 종료할 수 있게 while반복문을 작성해주고, 숫자들의 합이 S보다 크고, 사용된 숫자의 개수가 ans보다 작으면 결과값을 갱신해준다.(ans가 0일때는 무조건 시행)

4. 반복문 종료후 결과값을 출력해준다.

 

N, S = map(int, input().split())
numbers = list(map(int, input().split()))

cp1, cp2 = 0, 0
ans = 0
cnt = 1
check_value = numbers[0]
while cp1 < N and cp2 < N:
    if check_value >= S:
        if ans > cnt or ans == 0:
            ans = cnt 
    if check_value < S and cp2 < N-1:
        cp2 += 1
        cnt += 1
        check_value += numbers[cp2]
    else:
        check_value -= numbers[cp1]
        cp1 += 1
        cnt -= 1
print(ans)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.