[백준/약점체크] 1806번: 부분합

[문제]

 

[내 코드]

먼저 시간 초과 오류가 떴던 코드다

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

def finder(answer):
    while True:
        for start in range(N):
            end = start+answer
            if sum(li[start:end]) >= S:
                return answer
        answer += 1
    return 0

print(finder(0))

- answer를 두 인덱스의 간격으로 두고, 슬라이싱하여 합을 구했다

- 시간 초과 오류!!

 

그 다음, 통과한 코드다

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

startPointer = 0
endPointer = 0
total = 0
ans = []
 
while True:
    if total >= S:
        ans.append(startPointer - endPointer)
        total -= data[endPointer]
        endPointer += 1
    elif startPointer == N:
        break
    else:
        total += data[startPointer]
        startPointer += 1

if len(ans) == 0:
    print(0)
else:
    print(min(ans))

- 투포인터 알고리즘으로 풀어야 한대서, 투포인터 알고리즘을 구현한 코드를 조금 수정하여 제출해보았다 (게다가 원래 코드의 리스트는 오름차순의 sort된 리스트라고..)

- 처음 접근한 방식이 최소한의 거리에서 시작, 목표한 수에 다다르면 break - 였는데, 정답의 경우 목표한 수에 일단 다다른 다음에 거리를 좁혀가며 어디까지 가까워질 수 있는지 계산한다고 보면 될 것 같다

- 알고리즘을 꿰차고 있어야겠다는 생각이 들었다 이제라도 공부 시작해서 다행임

 

영 헷갈려서 그림 그려가며 이해하려 노력했다

startpoint를 먼저 이동시켜서 목표하는 수까지 간 다음 그 앞 인덱스의 값들을 빼주며(이것을 가리키는 게 endpoint) 계산한다

목표하는 수보다 작아지면 다시 startpoint를 이동한다

 

나는 여기에 S 이상이 됐을 때마다 리스트에 start와 end의 거리를 리스트에 담아주고, 가장 짧았던 거리를 출력하도록 했다

실행시간 140 ms