문제풀이/백준oj
[백준OJ] 15641번 SUPER SUPER BINARY SEARCH DELUXE 2.5: THE LEGEND OF THE GOLDEN MAZASSUMNIDA, EPISODE 2: THE MAZWAETL UNIVERSE, PART 2: THE PARALLEL UNIVERSE AND THE LOST MAZASSUMNIDA: GAME OF THE YEAR EDITION
Hyeon-Uk
2021. 5. 6. 00:51
반응형
15641번: SUPER SUPER BINARY SEARCH DELUXE 2.5: THE LEGEND OF THE GOLDEN MAZASSUMNIDA, EPISODE 2: THE MAZWAETL UNIVERSE, PART 2:
1 이상 100 이하의 자연수를 출력한다. 단, 하나의 자연수만 정답이다. 정답은 맞은 사람이 나타날 때마다 바뀐다. 정답보다 작은 수를 출력하면 33% 부근에서 "틀렸습니다"를 받는다. 정답보다 큰
www.acmicpc.net
-풀이-
이분탐색을 손으로 직접 해보라는 문제이다.
1이상 100이하의 숫자중 하나를 맞춰야한다. 처음엔 50을 제출해서 50보다 작으면 1~49 사이에 있다는 뜻이되고, 50보다 크다면 51~100사이에 있다는 뜻이된다. 이렇게 중간값들을 제출하며 UP, DOWN을 잘 맞춰서 제출을 하다보면 답이 나오게된다.
참고로 본인은 답이 1인 최악의 경우가 걸렸다.....
-시간복잡도-
1~100사이에서 이분탐색을 실행하면 되므로 O(logN)시간이 걸린다.
-코드-
Text 파일에다가 본인이 직접 이분탐색을 실시하며, 중앙값을 넣어 제출하면 된다.
반응형