반응형 두개의 포인터2 [C/C++] 백준 #2003 수들의 합 2(두개의 포인터) 두개의 포인터는 연속된 구간을 나타낼 수 있는 두개의 인덱스를 유지하면서, 그 구간의 결과가 해가 되는지 검사하는 방법입니다. 현재 영역에서 영역이 커지면 결과도 커져야 하고, 영역이 작아지면 결과도 작아져야 합니다. 이 조건을 만족하지 않으면, 사실상 두개의 포인터를 이용할 경우가 별로 없습니다. 양수들의 구간의 합은 위의 조건에 부합합니다. [a .. b] 구간에서 구간이 하나 증가하면, 구간의 합은 늘어나게 됩니다. 또한 구간이 하나 줄어들면, 구간의 합은 줄어들게 됩니다. 이를 이용해서 연속된 구간의 합이 M이 되는 곳을 찾을 수 있습니다. 시간 복잡도는 \(O(N)\)입니다. 제가 작성한 소스입니다. //------------------------------------------------ //.. 2023. 1. 14. [C/C++] 백준 #1940 주몽(두개의 포인터) 두개의 조합에 의해서 M인 값을 얼마나 많이 찾을 수 있는 가에 대한 문제입니다. 예를 들어서, 2 7 4 1 5 3 이라는 재료가 주어지고, 조합해서 만들어야 하는 갑옷이 9의 값을 가져야 한다면, 먼저 정렬을 수행합니다. 1 2 3 4 5 7 그러면 두개의 합을 왼쪽편과 오른쪽편을 이용해서 구해보도록 합니다. 1) 1 과 7을 더하면 8이므로 숫자가 부족하므로 왼쪽을 1 증가시킵니다. 2) 2 와 7을 더하면 9이므로 답을 1 증가시키고, 왼쪽을 1 증가, 오른쪽을 1 감소합니다. 3) 3과 5를 더하면 8이므로, 왼쪽을 1 증가합니다. 4) 4와 5를 더하면 9이므로, 왼쪽은 1 증가, 오른쪽을 1 감소합니다. 5) 왼쪽의 포인터와 오른쪽 포인터가 교차했으므로 종료합니다. 그러면 총 2개의 갑옷을 .. 2022. 11. 29. 이전 1 다음 728x90
