Ray`s Tech Lab

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

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1 복사

10

15 5 1 3 5 10 7 4 9 2 8

예제 출력 1 복사

2

[접근방식]

1. 배열의 첫 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

2. 배열의 두 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

3. 배열의 세 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

...이렇게 해서 각 단계에서 구한 길이 중 가장 짧은 놈을 고른다.

import sys

N, S = map(int, sys.stdin.readline().split())
length = []

arr = list(map(int, sys.stdin.readline().split()))

for i in range(len(arr)):
    j, sum = i + 1, arr[i]

    while(sum < S and j < len(arr)):
            sum += arr[j]
            j += 1
    if sum >= S:
        length.append(j - i)

if length:
    print(min(length))
else:
    print(0)

근데 위 코드는 시간초과가 발생한다. 왜일까?

우선 코드를 보면 난 for문에서 i를 시작점으로 설정하며 각 구간들을 구하는데, j라는 변수가 구간의 끝점역할을 한다. 따라서 구하는 구간의 합이 S이상이 되는 순간 구간의 길이인 j - i를 length리스트에 더하고 마지막에 min메소드로 가장 짧은 길이를 출력하면 그것이 정답이다. 근데 시간초과가 뜨는 이유는 다름아닌 j, sum와 관련되어 있다.

바로 매 순간 새로 측정을 시작할 때마다(즉 시작점 i가 바뀔 때마다) j를 i + 1로 세팅한 뒤, j를 늘려가면서 측정하기 때문! 이것이 시간을 잡아먹는다. 마찬가지로 sum을 매 측정마다 새로 설정해주는 것도 시간을 잡아먹는다. 왜 Why?

어떤 단계에서 합이 S이상이 되는 구간을 구했다고 할 때, 이 구간의 끝점이 있다.

다음 단계에서 합이 S이상이 되는 구간을 또 구할텐데, 이 때 새로 구하게 되는 구간의 끝점은 이전 단계에서 구한 구간의 끝점보다 같거나 클 수밖에 없기 때문! 따라서 매 측정의 단계에서 사용한 j와 sum을 그대로 재활용?하는 느낌으로 써주는 식으로 코드를 수정했다.

import sys

N, S = map(int, sys.stdin.readline().split())
length = []

arr = list(map(int, sys.stdin.readline().split()))
sum_arr, j = arr[0], 1

for i in range(len(arr)):           
    while(sum_arr < S and j < len(arr)):   
        sum_arr += arr[j]             
        j += 1
    if sum_arr >= S:                       
        length.append(j - i)
    sum_arr -= arr[i]                     

if length:                                
    print(min(length))
else:                                      
    print(0)

이런 방식?을 투포인터 알고리즘 이라 부르는 것 같다.

공부해봐야겠다..