4103 : 합이 K인 두 수의 쌍 개수2
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 4
•통과: 1
•만든사람: suakii
문제 설명
$1$부터 $N$까지의 자연수 중에서 두 수의 합이 정확히 $K$인 순서 없는 쌍 $(a, b)$ (단, $a < b$)의 개수를 구하는 프로그램을 작성하시오.
예를 들어 $N=10$, $K=11$이면 쌍은 $(1,10), (2,9), (3,8), (4,7), (5,6)$으로 총 5쌍이다.
[제약 조건]
• $2 \le N \le 1,000,000$
• $3 \le K \le 2,000,000$
• $N, K$는 정수
예를 들어 $N=10$, $K=11$이면 쌍은 $(1,10), (2,9), (3,8), (4,7), (5,6)$으로 총 5쌍이다.
[제약 조건]
• $2 \le N \le 1,000,000$
• $3 \le K \le 2,000,000$
• $N, K$는 정수
입력 설명
첫째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어집니다.
출력 설명
조건을 만족하는 순서 없는 쌍의 개수를 출력한다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
10 11
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5
도움
$N$이 최대 1,000,000이므로 $O(N^2)$ 2중 반복문을 사용하면 시간 초과가 발생합니다.
$a$가 결정되면 $b = K - a$가 자동으로 결정되므로, $O(N)$ 단일 반복문으로 해결하거나 가능한 $a$의 범위를 구하는 $O(1)$ 수학 공식을 활용하세요.
$a$가 결정되면 $b = K - a$가 자동으로 결정되므로, $O(N)$ 단일 반복문으로 해결하거나 가능한 $a$의 범위를 구하는 $O(1)$ 수학 공식을 활용하세요.