코드

# 최댓값
INF = int(1e9)

n, s = map(int, input().split())
arr = list(map(int, input().split()))

# 처음과 끝이 동일한 지점일 수 있음
start = 0
end = 0

# 부분합을 담을 변수
parts = 0

# 최종 정답을 담을 변수 (최소 개수를 담을 것이므로 INF로 초기화)
answer = INF

# end가 배열의 마지막에 도달할 때까지 반복 실시
while True:
    
    # 부분 수열의 길이
    # end-start-1이 아닌 이유
    # 직전의 연산에서 end는 +1이 증가한다 => 별도로 +1을 해줄 필요가 없음
    length = end - start
    
    # 부분합이 s보다 크다면
    if parts >= s:
#         print(start, end, length, parts, answer)
        
        # s보다 큰 경우의 부분 수열 길이를 구하는 것이므로
        # length와 answer 중 더 작은 값으로 answer를 업데이트 시킴
        answer = min(answer, length)
        
        # 아래 두 코드를 작성하는 이유
        # => 부분합이 큰 첫 구간을 구하는게 아니라 끝까지 구해서 가장 짧은 길이를 구해야 함 
        # => answer의 값이 업데이트 됐어도 다음 요소들이 남아있다면 부분합을 계속 갱신해줘야 함
        
        # 부분합에 맨 첫 요소의 값만큼 감소
        parts -= arr[start]
        
        # 첫 요소를 뺌 => start값을 1증가 시킴
        start += 1
        
    # end가 n과 값이 같아짐
    # => 배열의 마지막(n-1)까지도 다 반복을 실시했음
    # => 끝까지 부분합을 다 구했음
    elif end == n:
        break
        
    # s보다 작거나 같다면
    else:
        
        # 부분합에 마지막 요소를 더 해줌
        parts += arr[end]
        
        # end값 1증가
        end += 1
        
# answer의 값이 변경되지 않으면 INF => 0 출력
if answer == INF:
    print(0)
else:
    print(answer)

문제 해설

부분합을 투 포인터를 활용하여 해결하는 문제.

투 포인터 자체가 단순하여 쉽게 생각했다가 상당히 애를 먹은 문제이다. 로직 자체는 구현을 하였으나 아래의

# end가 n과 값이 같아짐
# => 배열의 마지막(n-1)까지도 다 반복을 실시했음
# => 끝까지 부분합을 다 구했음
elif end == n:
    break

이 분기를 파악하지 못해서 계속 오답 처리를 받았다. 결국 구글링으로 위와 같은 코드를 파악하여 한 줄 한 줄 별도의 공부를 하여 문제를 풀 수 있었다.

또한, 부분 수열의 길이를 담을 변수 length를 구하는 식이 end - start인 것도 이해하는데 시간이 걸렸다. 실제 만약 start가 1이고 end가 3인 경우, 부분 수열의 길이는 3-1+1 인 3이 되어야 한다. 허나, 코드에서 보면

length = end - start

위와 같이 계산하였다. 이유는 목푯값인 s보다 부분합의 값이 커지기 바로 직전의 조건문 연산인

 # s보다 작거나 같다면
else:   
    # 부분합에 마지막 요소를 더 해줌
    parts += arr[end]

    # end값 1증가
    end += 1

위의 코드에 있다. 코드를 보면 부분합을 증가시킨 후, end의 값 또한 1 증가하게 된다. 이런 경우, 당연히 부분합에 누적된 값은 arr[end-1]까지 누적돼있지만, 마지막 지점의 값은 end 즉, +1이 추가된 상태이다. 이 로직 후, s보다 부분합의 값이 커졌다면 다음은 아래의 조건문이 동작하게 된다.

length = end - start

# 부분합이 s보다 크다면
if parts >= s:

    # s보다 큰 경우의 부분 수열 길이를 구하는 것이므로
    # length와 answer 중 더 작은 값으로 answer를 업데이트 시킴
    answer = min(answer, length)

    # 부분합에 맨 첫 요소의 값만큼 감소
    parts -= arr[start]

    # 첫 요소를 뺌 => start값을 1증가 시킴
    start += 1

즉, end는 다음 연산을 위해 미리 1이 증가된 상태이므로 length 자체가 end - start + 1이 아닌 end - start로 구해야 하는 것이다.

알고리즘을 사용해서 구현을 하는 그 과정이 생각보다 많이 까다로웠다. 여러번 반복하여 문제를 계속하여 풀어봐야겠다.

댓글남기기

참고