16564번: 히오스 프로게이머
첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X
www.acmicpc.net
백준 16564번. 히오스 프로게이머 문제.
무난한 이분탐색 문제이다.
의식의 흐름.
음... 일단 K가 10억이니까 시간복잡도가 log인 계산이 무조건 들어가겠네.
이거 딱봐도 이분탐색으로 해결해야되네. lower_bound로 제발 해결 가능했음 좋겠다.
아씨 lower_bound로 어떻게 해결해야 되는지 안보여. 그냥 while문으로 구현한다.
해결 방법.
어차피 logK는 K가 10억이니까 최대 30번.
이분 탐색 안에서, for문으로 O(N)으로 특정 목표레벨일 때, 얼마나 올리는지 조사해도, 시간복잡도는 O(NlgK)이므로
2초 안에는 충분히 가능하다.
따라서, 이분탐색 안에서 for문으로 특정 레벨일 때 필요한 레벨업 수를 sum변수에 모은 후, K보다 크면 s=mid+1, K보다 작으면 e=mid-1 해준다.
sum==K일 때 뿐만 아니라, 작을 때 답이 되니까, ans=mid;로 중간에 처리해주자.
주의사항.
이분탐색은 항상 시작~끝 범위를 조심해야된다.
비교했을 때 당시의 mid값을 ans에 넣어줘야 하므로
끝에 ans=mid로 하고 s를 증가시켜야 한다.
else {
ans = mid;
s = mid + 1;
}
코드.
boj.kr/2b70c72c5ccb4bb3b3230358bf738500
공유 소스 보기
www.acmicpc.net
이 코드, 실수로 변수 하나 더 넣어서 메모리가 겁나게 크다는 차이밖에 없는데 왜 4ms더 빠를까...?
아래 코드가 정석 풀이다.
boj.kr/71b3aa10835041899c28f93c14be2ba5
공유 소스 보기
www.acmicpc.net
'PS > BOJ' 카테고리의 다른 글
| [BOJ] 백준 17131. 여우가 정보섬에 올라온 이유 (Platinum IV) (0) | 2021.03.31 |
|---|---|
| BOJ #1963. 소수 경로 (Gold 하위권) (0) | 2021.01.23 |
| BOJ #2229. 조 짜기 (Gold 하위권) (0) | 2021.01.22 |
| BOJ #15681. 트리와 쿼리 (Silver 상위권) (0) | 2021.01.20 |
| BOJ #5710. 전기 요금 (Gold 하위권) (0) | 2021.01.20 |