https://www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
문제 한줄 이해
- 수열의 부분합 중 합이 S이상인 것 중에 길이가 가장 적은 것을 구하기
생각난 풀이
문제를 읽고 생각난 필요한 조건들
1. 수열에는 10000이하의 자연수로 이루어져있다. -> 첫자리부터 더해가면 증가만 한다. -> 정렬의 효과
2. 부분합을 어떻게 구할것인지
-> 완전탐색을 통해 구할 수 있지만 N이 100000까지 가능하므로 시간초과 발생
-> 따라서 dp를 활용해 부분합 구하기
dp를 활용해 구하는 아이디어는 다음과 같다.
고등학교때 배운 수열을 생각해보자 이때 수열의 합을 구하기 위해 시그마를 썼었다.
이때 1~n까지의 합을 구해서 1~n-2까지의 합을 구해 빼준다면 n-1 ~ n까지의 합을 구해낼 수 있다.
3. 이제 두개의 포인터를 가지고 원하는 구간의 합을 계산해서 길이 구하기
dp[end] 값이 S보다 적다면 end +=1 why? 1번에서 정렬의 효과를 사용해서 작다면 포인터를 뒤로 옮겨주기
크다면 더이상 end포인터를 뒤로 갈 필요가 없다.
그래서 start포인터를 땡겨주기
import sys
n, m = map(int,sys.stdin.readline().split())
nlist = list(map(int,sys.stdin.readline().split()))
dp = [0] *(n+1)
for i in range(1,n+1):
dp[i] = dp[i-1] + nlist[i-1]
start = 0
end = 0
result = 1e9
while start <= end:
if end == n+1:
break
if dp[end] - dp[start] < m:
end +=1
elif dp[end] - dp[start] >= m:
if result > end - start:
result = end-start
start +=1
if (result == 1e9):
result = 0
print(result)
'알고리즘 > Python' 카테고리의 다른 글
[백준] 27172 - 수 나누기 게임 (0) | 2023.09.12 |
---|---|
[백준] 2467 - 용액 (0) | 2023.09.11 |
[백준] 16236 - 아기상어 (0) | 2023.09.03 |
[백준] 11779 - 최소비용 구하기 2 (0) | 2023.09.02 |
[백준] 2638 - 치즈 (0) | 2023.09.01 |