https://www.acmicpc.net/problem/7453
이런 문제는 컨디션을 많이 타는 느낌... 물론 이렇게 한번 익혀두고 나면 다음엔 컨디션 안좋아도 기억으로 풀지만 처음 겪는 문제일땐 컨디션 좋은날은 스스로 떠올리는데 컨디션 안좋은 날은 아무리 고민해도 떠오르지가 않는것같다.
그러니까 결국 경험을 늘려야겠지 뭐...
세로로 A, B, C, D 로 보면 되고 A + B + C + D = 0 이 되는 조합의 갯수를 찾는 문제
4중 for문을 돌리면서 0이 되면 count++ 하는 방법이 있겠지만 당연히 시간복잡도 over고
4개의 합이 아닌 2개의 합이었다면 투포인터로 접근 가능할거같은데? 라는 생각까지는 했다.
만약 2개라면 A정렬, B정렬 해서 A는 왼쪽부터, B는 오른쪽부터 투포인터로 오면서 계산하면 될텐데
이건 또 4개라 안되겠네라고 생각했었다.
근데 합이다
A랑 B 두개만 더한거, C랑 D 두개만 더한거 두 묶음으로 구해서 둘을 더해도 합이니까 괜찮다.
그래서 A와 B의 합으로 나올 수 있는 값들 2중for문으로 다 구하고
C와 D의 합으로 나올 수 있는 값들도 2중for문으로 다 구한다.
그 다음 AB에 있는거부터 돌면서 CD에 -1 * AB가 있는지 탐색해서 있으면 count++하는 것
다만 갯수가 많으니 정렬해서 이분탐색으로 upper - lower로 count
아니면 투포인터로 가면서 같은거 있는지 count
그니까 결국 핵심 아이디어는 두개씩 묶어서 두개로 만드는데 있다.
이게 참... 컨디션빨인지 경험빨인지...