[BOJ][2018번] 수들의 합 5

안녕하세요 Dibrary입니다.

이번에는 흔히 '투 포인터' 를 써서 풀어야 하는 문제를 정리해보겠습니다.

이번 문제는 단순히 합을 구하는 것입니다.

2018번: 수들의 합 5

 

---

우선 이 문제를 처음 보았을 때, '투 포인터'라는 개념 자체도 몰랐었습니다.

그래서, 가장 먼저 떠오른 생각은 '완전 탐색'이었죠. 문제는, N이 1000만까지 주어질 수 있는데, 그러면 1개씩 전부 끝까지 진행해보고, 2개씩 전부 끝까지 진행해보고, 3개씩 ... N-1개는 안되겠지만 이런방법으로 해야 완전탐색이 되는데, 대놓고 시간이 안될 거 같죠?

파이썬 기준으로 적어도 약 2천만번 연산이 1초라고 가정할 때, 위 방법으로는 수십초가 넘을 거 같네요...

 

그래서 찾아보니 '투 포인터'라는 게 있더라구요. 

사실 이 문제는 이미 '투 포인터'를 쓸 수 있다! 는 신호를 주고 있습니다.

문제를 잘 읽어보면 "연속된 자연수"로 나타내야 한다는 것이 그 신호입니다.

 

코드는 간단합니다.

start_idx가 있고, end_idx가 있습니다. 이 두 개가 포인터 처럼 되어서, 가리키는 값이 변하면서 이동하는 것이죠.

위 코드에서는 제가 start_idx, end_idx의 값을 추적해보고자 print를 추가했는데, 예제입력 15에 대한 출력은 아래와 같습니다.

보면 처음에 1부터 5까지 진행한 합이 15이므로 그 다음부터 end_idx가 1 늘어난 6을 가리키는 것을 볼 수 있습니다.

그 다음에 1부터 6까지의 합은 15보다 크므로 start_idx가 1 늘어나서 2를 가리키죠. 그 다음에도 15보다 크므로 계속 start_idx가 늘어나다가 4가 되면 4+5+6은 15이므로 이때 count값이 늘어납니다.

계속해서 start_idx와 end_idx가 위치를 바꿔가며 start_idx ~ end_idx의 합이 15(n)인지를 확인합니다. 이게 '투 포인터' 방법입니다.

 

코드를 잘 보시면 count값은 처음에 1로 들어가있죠.
항상 하던 방법대로 0을 넣어서 갯수를 세지 않습니다. 왜 그럴까요?

왜냐하면, while문은 end_idx != n으로 되어 있기 때문입니다. end_idx가 n이 되어버리면 while문 내부는 실행하지 않고 종료됩니다. 그렇지만 n이라는 값이 주어졌을 때, 해당 n 한 개만 선택하는 방법은 '반드시' 존재하죠.
그걸 미리 count = 1로 넣어놓은 것입니다.