반응형
문제
https://www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
풀이
투 포인터 알고리즘으로 풀 수 있는 문제입니다.
양 끝에 포인터를 놓는 것이 아닌 왼쪽에 두개의 포인터를 두어서 풀이해야 합니다.
합이 s이하라면 하나의 포인터를 계속해서 늘려주고,
s이상이 된다면 또 다른 하나의 포인터를 늘려주어서 길이를 구할 수 있습니다.
소스코드
후기
양 끝에 포인터를 두는 방식으로 투 포인터 알고리즘을 써왔었는데,
한쪽에서 출발하는 방법도 있다는 것을 알게되었습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 1450 냅색문제 (Swift) (0) | 2023.05.03 |
|---|---|
| [BOJ] 백준 1644 소수의 연속합 (Swift) (0) | 2023.05.03 |
| [BOJ] 백준 2470 두 용액 (Swift) (0) | 2023.04.30 |
| [BOJ] 백준 3273 두 수의 합 (Swift) (0) | 2023.04.28 |
| [BOJ] 백준 1956 운동 (Swift) (0) | 2023.04.28 |
