[BOJ] 1806. 부분합

문제

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

 

 

 

---

 

주요 아이디어

처음에는 혹시 될까 해서 그냥 풀어보았다.

말 그대로 하나씩 잘라보면서 최소값을 갱신하는 방식...

---

 

코드 구현 (Python 3)

 

# 길이 N, 합 S
n, s = map(int, input().split())
# 수열
numbers = list(map(int, input().split()))

total = 0
min_len = 10**8 + 1 # s 최대값

# 벌써 O(n^2) 나오죠
for i in range(len(numbers)):
    for j in range(i, len(numbers)):
        arr = numbers[i:j]
        if sum(arr) >= s:
            if min_len > len(arr):
                min_len = len(arr)
            break

if min_len == 10**8 + 1:
    print(0)
else:
    print(min_len)

 

역시나 시간 초과 발생

---

 

실패 원인

코드를 살펴보면, 처음부터 끝까지 도는 중첩 반복문이므로 벌써 시간 복잡도가 O(n^2)가 나온다.

이 문제는 "투 포인터"를 이용해야 하는 방식이다.

• low, high를 둔다
• 합이 같거나 클 경우 low에 1을 더해 범위를 좁힌다
• 합이 작을 경우 high에 1을 더해 범위를 늘린다
• 끝에 도달할 경우 반복문을 종료한다

 

---

 

코드 재구현 (Python 3)

# 길이 N, 합 S
n, s = map(int, input().split())
# 수열
numbers = list(map(int, input().split()))

total = 0 # 맨 처음 인덱스값
min_len = n + 1 # s 최대값

low = 0; high = 0

# 원소 끝에서 달성되는 경우
while True:
    # print(f'## low : {low}, high : {high}')
    # 매번 sum 계산하지 말고 total에다가 더하고 빼기
    # 합이 아직 작을 경우 -> high 범위 늘리기
    if total >= s:
        min_len = min(min_len, high-low)
        total -= numbers[low]
        low += 1
    # 끝에 도달하면 break
    elif high == n:
        break
    # 합이 같거나 크면 -> low 범위 좁히기, 더 작은 범위 찾아보기
    else:
        total += numbers[high]
        high += 1
    # print('## total : ', total)

# 끝까지 돌았는데도 안나옴 (high가 n에 도달) -> 결과 없는 것
if min_len == n+1:
    print(0)
else:
    print(min_len)

이렇게 하면 O(n)으로도 문제를 해결할 수 있다!

---

 

제출 결과