📚 문제
https://www.acmicpc.net/problem/1637
📖 풀이
정수가 엄청나게 많다. 최대 대략 10억 * 20000번의 연산이 필요하므로 담는 순간 시간초과가 발생한다.
매개변수 탐색을 활용해본다. 홀수개 존재하는 정수가 하나만 있으므로 특정 정수 이하의 개수를 센다.
그러면 다음과 같이 나온다.
짝 짝 짝 짝 홀 홀 홀 홀 홀 홀 ....
왜냐하면 홀수개 존재하는 정수보다 작은 특정 수 이하의 정수들의 개수는 무조건 짝수이다.
홀수개 존재하는 정수보다 크거나 같은 정수 이하의 개수들은 무조건 홀수가 나온다.
예를 들면,
1: 2
2: 2
3: 2
4: 3
5: 2
6: 2
위처럼 수들이 존재한다고하면 4만 홀수개 존재할 때이다. 이 때 4보다 작은 정수 이하의 개수를 세면 무조건 짝수가 나온다.
ex). 1이하의 정수는 2, 2이하의 정수는 4, 3이하의 정수는 6
홀수개 존재하는 4보다 크거나 같은 정수 이하의 개수는 무조건 홀수이다.
ex). 4이하의 정수는 9, 5이하의 정수는 11, 6이하의 정수는 13
따라서 특정 정수 이하의 정수들의 개수가 홀수인 것 중 가장 작은 값을 찾으면 그 때가 우리가 찾는 홀수개 존재하는 정수이다. 홀수가 True라고 하면
xxxxxooooooooooo...
위와 같이 탐색할 수 있다. 그러면 이진탐색을 활용해 매개변수 탐색을 통해 True가 나온 값 중 맨 왼쪽 값을 구한다. 그러기 위해 True가 나오면 mid 오른쪽을 버리고, False가 나오면 mid 왼쪽을 버리며 탐색해나간다.
이제 x이하의 정수들의 개수를 탐색하기 위한 함수를 작성한다.
입력 받은 a, c, b는 range로 생각하면 (a, c + 1, b)이다. 이 때 내가 구한 x가 이 구간 안에 몇 개가 속해있는지 찾으면 된다.
일단 x가 a보다 크거나 같아야 하나 이상 존재한다.
그리고 x가 a보다 크면 x - a와 c - a 중 최소 값을 골라 b로 나눈 몫에 1을 더해준다.
x와 c 중 최소값을 고르는 이유는 최댓값인 10 이후로 더 수가 나올 수 없기 때문이다.
몫에 1을 더하는 이유는 A + B, A + 2B ... 만 있는게 아니라 A도 있기 때문에 1을 더해준다.
입력받은 20000개 모두 해주고 나온 결과를 더해주면 x 이하의 정수들의 개수를 구한 것이다.
그러면 이 때 홀수이면 True를 리턴하고, 짝수이면 False를 리턴한다.
그리고 정수가 몇 개 들어있는지 출력해야 하기 때문에 x의 개수를 찾는 함수를 하나 더 만든다.
이 때는 위에 구했던 함수가 몫을 구하는 연산을 했다면 모듈러 연산을 통해 안에 있는지 확인하면 된다.
그리고 a보다 크거나 같고 c보다 작거나 같을 때 x - a가 b로 나누어 떨어지는지 확인하면 된다.
그 때 나온 값들을 모두 더한 값이 개수이다.
홀수개 존재하는 정수가 무조건 있는지 알았는데 없는 경우도 존재했다.
이 때에는 NOTHING을 출력하도록 조건문을 작성한다.
📒 코드
import sys
input = sys.stdin.readline
def check(x): # x이하의 정수들의 개수가 홀수인지 체크
cnt = 0
for a, c, b in arr:
if a <= x: # a보다 크거나 같은 경우만 있다.
cnt += min((c - a), (x - a)) // b + 1 # 몫을 활용
if cnt % 2: # 홀수면 True
return True
else:
return False
def counting(x): # x의 개수를 찾는다.
cnt = 0
for a, c, b in arr:
if x < a or x > c:
continue
if (x - a) % b == 0: # 모듈러 연산으로 값이 있는지 확인
cnt += 1
return cnt
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
s, e = 1, 2_147_483_647
ans = -1
while s <= e: # 이진탐색
mid = (s + e) // 2
if check(mid): # x이하의 정수들의 개수 홀수인 것중 가장 작은 정수를 찾는다.
ans = mid # 매개변수 탐색
e = mid - 1
else:
s = mid + 1
if ans == -1: # 없으면 NOTHING 출력
print('NOTHING')
else:
print(ans, counting(ans))🔍 결과
