1637 날카로운 눈

숫자의 범위는 1~ 2147483647 (2^31 - 1)

입력이 최대 2만개
1 2147483647 1입력이 2만개 들어오면 21억 번 * 2만번 -> 시간초과


숫자를 저장하지 않고 답을 구해야된다.
숫자의 범위로 계산하면 좋을듯하다.

단 하나의 숫자만 홀수개이다.
아예 홀수개인 숫자가 없을 수도 있다.

단 하나의 숫자만 홀수이기때문에, 홀수가 속한 범위의 개수의 합은 홀수가 된다.
홀수가 속하지 않은 곳의 범위의 개수의 합은 짝수가 된다.

특정 수가 홀수이다.
특정 수가 속한 범위의 개수는 홀수개다.
특정 수가 속하지 않은 범위의 개수는 짝수개이다.

특정수를 정한다.
특정수가 속한 범위의 개수를 구한다.? 


지금 저게 각각의 정수 더미가 아니라 하나의 정수더미다.
하나의 정수더미라고 생각해라 

1 2 2 3 3 3 3 5 5 7 7 8 8 8 8 8 8 10

1 2 3 4 5 6 7 8 9 10 11 12 13
0 2 0 2 0 5 0 2 0 2    0   2  0
이런식으로 숫자와 숫자의 개수가 매핑되어있다고 생각해보자


1에서 mid까지 범위의 숫자의 개수의 합이 짝수라면 
1~mid 까지에는홀수인 숫자가 없다.

근데 1~mid까지 범위의 숫자의 개수의 합이 홀수라면
1~mid사이에는 홀수인 숫자가 있다.

하나의 숫자만 홀수이기 때문에, 홀수가 속한 범위의 숫자 개수는 홀수
홀수가 속하지 않은 숫자 범위의 개수의 합은 짝수

어떤 숫자 (mid)를 결정했다.
[1,mid]범위의 숫자의 개수의 합을 더했을때 짝수라면 [1,mid]내에는 홀수개인 숫자가 없다.
그래서 l = mid + 1로 할당한다.

[1,mid]범위의 숫자의 개수의 합이 홀수인 경우, 해당 범위에 홀수개인 숫자가 있다.
적어도 mid보다 작기 때문에 mid를 저장한 뒤 , e를 mid - 1로 할당한다


a c b의 숫자가 들어왔을 때
a c b로 생기는 정수 중 빠르게 mid보다 작은 숫자들의 개수를 세어야한다.

a c b로 생기는 숫자들 중에 mid보다 작은 숫자들의 개수 찾기
=> 반복문 안쓰고 어떻게 찾을 수 있을까?

 

Q ) 첫번째 항이 a이고 등차수열이 b인 수들이 특정 값보다 작은 수의 갯수를 구하고 싶어.

A )

등차수열에서 특정 값보다 작은 수들의 개수를 구하는 방법을 설명할게요.

등차수열의 일반항은 다음과 같습니다: an=a+(n−1)⋅ba_n = a + (n - 1) \cdot ban​=a+(n−1)⋅b 여기서:

• aaa는 첫 번째 항
• bbb는 공차
• nnn은 n번째 항

특정 값 xxx보다 작은 수들을 구하려면 an<xa_n < xan​<x를 만족하는 nnn의 최대 값을 찾아야 합니다.

1. 등차수열의 조건을 세우기: a+(n−1)⋅b<xa + (n - 1) \cdot b < xa+(n−1)⋅b<x 이 부등식을 풀어보면, n−1<x−abn - 1 < \frac{x - a}{b}n−1<bx−a​ n<x−ab+1n < \frac{x - a}{b} + 1n<bx−a​+1
2. n의 최대값 구하기: 위 부등식에서 nnn은 정수이므로, 이 식을 만족하는 최대 nnn은 다음과 같이 구합니다: n=⌊x−ab+1⌋n = \left\lfloor \frac{x - a}{b} + 1 \right\rfloorn=⌊bx−a​+1⌋

a + ( n - 1 ) 
a + (n - 1) * b <= mid
(n - 1 ) <= (mid - a) / b
n <= (mid - a) / b + 1

근데 b의 값이 mid특정값보다 큰 경우에는 a + (n - 1 ) * b < mid여야 한다.

 

https://kibbomi.tistory.com/205

boj, 백준) 1637. 날카로운 눈 (C/C++)

출처 : 선생님 덕분에 이해했습니다..