반갑습니다!

1072번: 게임 www.acmicpc.net 풀이 해당 문제는 이분 탐색으로 해결할 수 있다. mid 값을 '형택이가 앞으로 하게될 게임의 개수'로 잡고 이분 탐색을 하면 된다. 승률 Z는 (Y x 100) / X 로 구할 수 있는데, 이 때 주의해야할 것은 Y x 100이 int 범위를 벗어날 수 있기 때문에 long long형으로 선언해야한다. 코드 #include #include #include using namespace std; long long x, y; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> x >> y; int left = 1; int right = 1000000000; int ans = num..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 효율성 테스트가 있는 문제이다. 따라서 효율성이 중요한 문제인데, 이 문제는 이분탐색을 사용해서 해결할 수 있다. 이분 탐색에서 가장 중요한 것은 '어떤 값을 기준으로 정할 것인가'이다. 아래의 코드에서는 니니트 프렌즈를 번호를 기준으로 했다. m번째 인원이 건널 때 디딤돌의 숫자는 stones[i] - m 이 되고, 이를 통해 건널 수 있는지 없는지를 파악해 이분 탐색해서 해결해주었다. 코드 C++ #include #include #include using namespace std; // m번째 인원이..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이분탐색으로 해결하는 문제이다. 이분탐색을 조금 응용해서 풀어야한다. 이분탐색에서 가장 중요한 것은 탐색의 기준으로 잡는 것이다. 이 문제에서는 mid를 기준으로 해서 돌들을 순차 탐색하고, mid보다 돌들간의 거리가 짧으면 돌을 제거한다. 그렇게 했을 때 제거된 돌의 개수가 n보다 작거나 같으면 mid 값을 증가시키고, n보다 큰 경우에는 mid값을 감소시켜 이분탐색한다. 코드 #include #include #include using namespace std; int solution(int dista..

1300번: K번째 수 www.acmicpc.net 풀이 문제에 써있는 그대로 구현해서는 풀 수 없다. 이분탐색을 이용해서 해결하였는다. 이분탐색을 하는 아이디어는 다음과 같다. 임의의 숫자를 정해서 그 수보다 작은 수들의 개수를 세었을 때, 총 개수가 K인 경우를 확인한다. 이 아이디어를 사용할 수 있는 이유는 정렬된 일차원 배열에서 K번째 수라는 것은 결국 K번째로 작은 수라는 말이기 때문이다. 그렇다면 이제 K보다 작은 수를 세는 방법을 알아보자. 이 문제는 N이 최대 100000 이므로 100000 x 100000 크기의 배열을 생성해서는 해결할 수 없다. 예를 들어 N이 3인 상황에 5보다 작은 수를 찾고 싶은 상황이라고 하자. 1x1 1x2 1x3 2x1 2x2 2x3 3x1 3x2 3x3 의..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이분탐색으로 해결한 문제이다. 초기 값으로 left를 1, right는 times 중의 최댓값 x n으로 설정하고 이분탐색을 하였다. mid = (left + right) / 2라고 하면 mid / times[i] 값은 mid 시간동안 i번째 심사관이 검사할 수 있는 사람의 수이므로 검사할 수 있는 사람의 수를 모두 더한 값과 n을 비교하며 이분탐색하면 해결할 수 있다. 코드 #include #include #include #include using namespace std; long long solut..