https://www.acmicpc.net/problem/25620
문제요약
- 슬라임이 주어짐(0~10^9, 20만개)
- 약을 사용할 수 있음(x이하를 y배, 0~10^9, 20만개)
- 약을 다 사용하고 슬라임을 오름차순 정력
접근법
- 숫자가 아무리 커져도 10^18임. 무한히 커지지는 않음
- 10^9까지는 조건에 걸릴테고, 10^9가 되기 위해서는 2^30. 즉 한 슬라임에 대해서 최대 30번 정도 연산을 수행할 수 있음
- 20만 * 30 = 600만, 전체 연산은 대략 600만일 것임
- 하나씩 다 해보고, 숫자가 10^9를 넘어가면 따로 빼놓아도 되긴 하는데, x보다 작은 숫자를 찾는 것을 매번 한다면 시간이 많이 걸릴 것임
- x보다 작은 숫자위주로만 고르면 600만의 곱하기 연산만 가져갈 수 있겠음
- x보다 작은 숫자를 찾기 위해서 우선순위 큐를 사용해서 관리함
- y=0이면 이후로는 계속 0이니까 별도 처리
- y=1이면 아무것도 안하고 넘어가기
newbieski