문제
출처 : www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
수열의 길이 N과 만들어야할 최소 수 S가 주어진다.
수열의 각 원소들의 합이 S이상이 되는 최소 길이를 구하는 문제다.
풀이
N이 최대 10만까지 가기때문에, 최악의 경우 100001 * 50000번 반복해서 시간초과가 난다.
투포인트로 풀었는데,
수열의 인덱스를 나타내는 변수 p1, p2를 선언한다.
p1 ~ p2의 합이 S보다 커질때까지 p2를 증가시킨다.
이때, 합이 S보다 커지면 p1을 증가시키며 길이를 줄인다.
이렇게 하면 p1최대 증가시키는데 N번 p2증가 N번 반복하여 O(2N)번에 풀수있다.
소스코드
https://github.com/devxb/JJUNalgo/blob/master/1806%20%EB%B6%80%EB%B6%84%ED%95%A9/main.cpp
devxb/JJUNalgo
백준 알고리즘 소스코드🙃. Contribute to devxb/JJUNalgo development by creating an account on GitHub.
github.com
'알고리즘 (2020 : 08 : 10 ~ ) > 구현, 시뮬' 카테고리의 다른 글
| [백준 / BOJ] 13460 구슬 탈출 2 (0) | 2021.01.04 |
|---|---|
| [백준 / BOJ] 9466 텀 프로젝트 (0) | 2021.01.03 |
| [백준 / BOJ] 8982 수족관 1 (0) | 2020.12.24 |
| [백준 / BOJ] 2495 연속구간 (0) | 2020.12.23 |
| [백준 / BOJ] 1083 소트 (0) | 2020.12.03 |