반응형
부분합
-
백준 1806 - 부분합백준 algorithm 2021. 11. 1. 23:02
=> 투 포인터 알고리즘의 개념을 알면 풀 수 있는 문제입니다. (저도 이 문제를 풀면서 처음으로 해당 알고리즘을 들었습니다.) => start 점과 end 점의 위치를 변환해가며 S의 값을 넘으면 가장 적은 길이를 찾아내는 방법입니다. => while문에서는 end가 0 인경우에 값을 부분합에 포함하지 않으므로, 이전에 값을 더해주는 과정이 필요합니다. => while문을 통해 start 점이 end점을 앞서지 못하도록 하며, end점이 N(배열 원소의 개수)를 넘지 못하도록 합니다. (배열의 끝점 = (원소의 갯수 -1) ) => 부분합이 S를 넘지 못할 경우 end점을 뒤로 한 칸 미루며 다시 한번 계산합니다. => 부분합이 S인 경우, 최소값을 구하고 다시 한번 end점을 뒤로 미룹니다. ( 이후..