Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 백준
- CSS
- lob
- PHP 웹페이지 만들기
- The Loard of BOF
- 드림핵
- 생활코딩
- BOJ
- 머신러닝
- 숙명여자대학교 정보보안 동아리
- c
- XSS Game
- WarGame
- SWEA
- siss
- BOJ Python
- Python
- 웹페이지 만들기
- 파이썬
- Sookmyung Information Security Study
- hackctf
- 풀이
- Javascript
- c++
- 숙명여자대학교 정보보안동아리
- HTML
- hackerrank
- 자료구조 복습
- 기계학습
- C언어
Archives
- Today
- Total
혜랑's STORY
[BOJ_C++] 13777번 : Hunt The Rabbit 본문
# 문제
- 1부터 50까지의 봉투 중 토끼가 들어있는 봉투를 알려준다.
- 봉투를 열어볼 땐 이분법을 사용한다. 따라서 맨 처음 열어보는 봉투는 항상 25가 된다.
- 이 때 열어보는 봉투를 모두 출력하라.
# 풀이
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int low, high, mid;
int key; cin >> key;
while (key != 0) {
low = 1, high = 50;
while (low <= high) {
mid = (low + high) / 2;
cout << mid << " ";
if (mid == key) break;
if (mid < key) low = mid + 1;
else high = mid - 1;
}
cout << "\n";
cin >> key;
}
return 0;
}
- 입력받은 key가 0이라면 프로그램을 종료한다.
- 항상 봉투가 있는 범위는 1부터 50이기 때문에 low와 high를 1과 50으로 초기화 한다.
- low <= high인 동안 mid = (low + mid) / 2가 되고 이 값을 출력한다.
- mid가 key와 같다면 반복문을 탈출한다.
- mid가 key보다 작다면 key의 범위가 mid의 오른쪽이 되야한다. 따라서 low = mid + 1이 된다.
- mid가 key보다 크다면 key의 범위가 mid의 왼쪽이 되야하고 low = mid -1이 된다.
- 프로그램이 종료될 때 까지 반복한다.
# 결과
'무지성 공부방 > 알고리즘 해결' 카테고리의 다른 글
[BOJ_C++] 1463번 : 1로 만들기 (0) | 2021.07.30 |
---|---|
[BOJ_C++] 1003번 : 피보나치 (0) | 2021.07.30 |
[BOJ_C++] 2776번 : 암기왕 (0) | 2021.07.26 |
[BOJ_C++] 2805번 : 나무 자르기 (0) | 2021.07.26 |
[BOJ_C++] 1759번 : 암호만들기 (0) | 2021.07.21 |