[BOJ] 2003번: 수들의 합 2

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

 

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

풀이

투포인터를 사용하여 풀었다.

 

-첫번째 시도

N, M = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0

for i in range(N):
    for j in range(i, N):
        if sum(A[i:j+1]) == M:
            cnt += 1
            break
        
print(cnt)

N, M, A를 입력받고, 이중 for 반복문을 이용하여 모든 경우의 수를 따지고자 했다.

만약 더한 값이 M이 되었을 경우, 이후에 j 반복문으로 다른 수를 더 더해봤자 M을 초과하므로 j 반복문을 바로 break했다.

그러나 시간초과!!!가 발생하여 while 문으로 해결하고자 했다.

 

-두번째 시도

N, M = map(int, input().split())
A = list(map(int, input().split()))
i, j = 0, 0
cnt = 0

while j < N:
    if sum(A[i:j+1]) == M:
        cnt += 1
        i += 1
        j = i
    elif sum(A[i:j+1]) > M:
        i += 1
        j = i
    else:
        j += 1
print(cnt)

오른쪽 포인터를 담당하는 j가 N보다 작을 경우에만 반복하도록 했다. 로직은 첫번째 시도의 for문과 비슷하다.

더한 값이 M이면 왼쪽 포인터인 i를 증가했다. 더한값이 더 크면 j를 더 키워봤자 계속해서 커지기만 하므로 i를 증가했다.

더 작을 경우에만 j를 증가시켰다.

그러나 여전히 시간초과 발생!!!

새로 알게된 사실! 원래 sum 같은 메소드는 아무런 생각없이 그냥 사용했는데, 이 경우에도 i부터 j까지 더하는 것이므로 시간이 꽤나 걸린다고 한다...(사실 당연함 ㅜㅜ)

 

-세번째 시도

그래서 이번에는 temp라는 변수에 sum값을 넣어줬다

N, M = map(int, input().split())
A = list(map(int, input().split()))
i, j = 0, 0
cnt = 0

while i <= j and j < N:
    temp = sum(A[i:j+1])
    if temp == M:
        cnt += 1
        i += 1
        j = i
    elif temp > M:
        i += 1
        j = i
    else:
        j += 1
print(cnt)

통과!