반응형 두 포인터1 [C/C++] 백준 #1806 부분합(두 포인터) 이번 문제는 두개의 포인터를 운용해서 푸는 방법입니다. 부분합인데 연속된 수열의 부분합이란 점이 문제를 푸는데 있어서 중요합니다. 예를 들어서 1 3 2 4 7 8 3 6 이란 수열이 있다고 하죠. 여기서 부분합이 20이상일 때 최소의 N을 구하도록 하면요. 처음부터 누적하여 부분합이 20이 넘는 곳을 찾습니다. 1 3 2 4 7 8 3 6 1 4 6 10 17 25 그러면 8에서 멈추게 되는데, 이 때부터는 앞에서부터 하나씩 제거해서 20 미만이 되는 시점을 찾습니다. 그러면 4의 숫자에서 멈추게 됩니다. 여기서 다시 오른쪽 숫자를 포함하면서 20 이상이 되는 지점을 찾습니다. 왜 앞에서부터 다시 안 찾는가하면, 이미 바로 앞의 숫자를 포함하고 뒤의 숫자를 포함하는 것은 의미가 없기 때문입니다. 최소의.. 2022. 10. 22. 이전 1 다음 728x90
