문제
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)으로도 문제를 해결할 수 있다!
제출 결과
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 15683. 감시 (1) | 2024.05.21 |
---|---|
[BOJ] 13414. 수강신청 (0) | 2024.05.21 |
[BOJ] 9466. 텀 프로젝트 (0) | 2024.04.24 |
[BOJ] 12852. 1로 만들기 2 (0) | 2024.04.24 |
[BOJ] 1463. 1로 만들기 (0) | 2024.04.21 |