[백준 / BOJ] 19637 IF문 좀 대신 써줘

문제

출처 : www.acmicpc.net/problem/19637

19637번: IF문 좀 대신 써줘

게임 개발자 밀리는 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다. 

캐릭터는 자신보다 큰거나 같은중에 가장작은수를 기준으로 칭호를 받는다

 

예를들어,

캐릭터의 전투력이 10이고

전투력이 10 보다 작거나같으면 A칭호를 받을때,

A칭호를 받게된다.

 

풀이

칭호의 갯수가 100000 = 10만개 나올수있고 캐릭터의 수가 10만개 나올수있다.

따라서 완전탐색으로 찾을려고 할경우, 최악일때 10만 * 10만이 되서 시간초과가 난다.

 

이분탐색 알고리즘이 한번 도는데 시간복잡도가 logN이므로, 최악의경우

100000log100000번 만에 모든경우를 다 찾을수있다.

 따라서 이분탐색으로

자신보다 크거나 같으면서 가장 작은 숫자를 찾으면된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/19637%20IF%EB%AC%B8%20%EC%A2%80%20%EB%8C%80%EC%8B%A0%20%EC%8D%A8%EC%A4%98/main.cpp

devxb/JJUNalgo