목록백준 1896 (1)
엠블란스휘호휘호
BOJ_1806 부분합(C++)
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 부분합 문제입니다. 0.5초의 제한시간을 가지고 있어 선형시간을 가지는 알고리즘을 생각했습니다. 주어진 예제에서 시뮬레이션 아이디어는 다음과 같습니다. 파란색 화살표에서는 S이상의 부분합을 찾은 상황으로써, start 인덱스를 증가시킬 수 있다면(증가시켜도 S이상이라면) 증가시키고 그럴수 없다면 last 인덱스를 증가시켜가며 최단 길이를 찾습니다. 빨간 화살표에서는 파란색 화살표에서..
프로그래밍/알고리즘
2021. 5. 8. 01:37