You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
문제 링크
https://www.acmicpc.net/problem/1253
문제 조건
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 "좋다"고 한다.
N개의 수가 주어질 때 좋은 수의 개수를 몇 개인지 구하라.
아이디어
정답의 최대치
최대치인 두 수의 합은 10억 + 10억 = 20억으로 int 자료형 범위 안에서 해결 가능하다.
방법 1) 완전탐색
각 원소마다 나머지 원소들을 전부 더해보면서 확인한다.
총 O(N^3)으로 시간 안 풀이가 불가능하다.
방법 2) 투포인터
L, R 포인터를 양쪽 끝에서 시작해서 더해준다.
시간 복잡도
배열을 정렬하는데 O(N logN) 타겟을 결정하는데 O(N) 타겟마다 투 포인터로 다른 수 2개 결정하는 데에 O(N)으로 총 O(N^2)의 시간이 걸린다.
시간 안 풀이가 가능하다.
구현
All reactions