백준 3273 - 두 수의 합

백준 3273 - 두 수의 합

https://www.acmicpc.net/problem/3273

풀이

단순하게 문제에 접근해보면, n 개의 수열 중 2개를 뽑아 조건을 검사하는

$ O(N^2) $ 의 풀이로 생각해볼 수 있다. 하지만, n의 범위를 살펴보면 O(N) 시간의

풀이를 적용해야 함을 확인할 수 있다. 다양한 풀이가 있겠지만, 투-포인터 알고리즘과

배열을 이용한 풀이를 사용할 수 있다. 문제의 입력으로 주어지는 수열을 저장하는 배열과

조건을 확인할 수 있도록 하는 bool 배열을 선언하고, 조건에 만족할때마다 cnt 변수를

증가시켜준다.

코드

추가 풀이

투-포인터 알고리즘을 사용해서도 해결 가능하다.

n 개의 수열을 입력받아 정렬한 후, 첫 인덱스와 마지막 인덱스를 포인터로 지정하고,

두 포인터의 합에 따라 포인터를 이동시키며 답을 구한다.

코드