안녕하세요,
재재입니다.
BOJ 2855 흥미로운 수열 문제에 대한 풀이입니다.
BOJ 2855 흥미로운 수열
(1) 문제 설명
분류 : bruteforce, 구현
출처 : https://www.acmicpc.net/problem/2855
흥미로운 수열이란,
2k개로 이루어진 수열이 있을 때,
처음 k개의 수열과 이후 k개의 수열의 원소의 합이,
(20억 이하) S를 넘지 않는 수열입니다.
(100,000 이하) N개의 수열이 주어졌을 때,
각 원소에서 시작하는 부분 수열 중,
가장 긴 흥미로운 수열의 길이를 구해주면 된다.
(2) 이 도출
i 번째 원소부터 왼쪽으로 합이 S를 넘지 않도록 하는 부분의 위치와,
i+1번째 원소부터 오른쪽으로 합이 S를 넘지 않도록 하는 부분의 위치를 안다면,
이 문제를 쉽게 해결 할 수 있습니다.
또한, 이것은 누적합과 upper bound를 활용하면 구할 수 있습니다.
BOJ 2855 흥미로운 수열