백준 2295 c++ (1) 썸네일형 리스트형 [백준 / C++] 2295번 세 수의 합 풀이 처음 문제를 읽었을 때는 N의 개수가 최대 1000개니 sorting한 이후 3개씩 슬라이딩 윈도우로 브루트포스 방식을 취하면 풀리지 않을까 생각하였으나, 슬라이딩 한 것들을 다시 확인 하는 방법에서 막혔고 다시보니 중복되게 선택할 수 있었다. 이후 map을 이용해 for문 3개 중첩을 무지성으로 시도하다 생각해보니 N3logN 이라 시간 초과 문제가 생겼다. (1000개를 3제곱하면 최소 10억이라 10초다. 심지어 map은 메모리 초과문제도 생겨 set으로 변경하였다) 더 이상 줄일 방법을 찾지 못해 힌트를 보았다가 다들 천재인가 싶었다. 풀이 방법은 간단하다. x,y,z 를 따로 구하지 않고 y,z를 합으로 한 배열(sum)을 하나 생성한다 (N2) 기존 배열을 arr라고 가정했을 때 x + y +.. 이전 1 다음
