algorithm/Binary Search 6

백준 2792 보석상자

https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 📌 해결과정 우선 문제를 읽고 문제를 풀기위해 필요한 조건들을 정리했다. 학생들의 질투심을 최소화 한다 = 한 학생이 갖는 같은 색상의 보석의 갯수를 최소화 한다 1. 모든 보석을 남김없이 학생들에게 나누어 줘야한다. 2. 한 학생은 같은 색상의 보석만 가질 수 있다. 3. 보석을 갖지 못하는 학생이 있을 수 있다. 어떻게 풀어야 할지 감을 잡지 못하다가 두번 째 예시를 통해서 힌트를 얻고 풀었다...

백준 6236 용돈 관리

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 📌 해결순서 정말정말정말 오래걸렸다 얼마동안 붙잡고 있었는지에 대한건 기억도 나지 않는다.. 이 문제를 오래붙잡고 있었던 이유가 있는데, 하루에 돈을 두번 뽑을 수 있다고 생각하고 문제에 접근했기 때문이다 예를 들어서 뽑는 금액이 300이고 첫날 사용하는 금액이 500 이면 돈을 두번 뽑아서 600을 만들고, cnt +=2 해주고 시작하면 되지 않을까 했지만 문제에서는 "모자라게 되면 남은 금액은 통장..

백준 3079 입국심사

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 📌 해결순서 문제를 다 읽고, 이해는 되는데 도저히 어떻게 풀어야 할지 감이 안잡혀서 2일정도 붙잡으면서 풀이를 생각했던 문제다... 이게 이분탐색이라고??? 왜??? 이 생각을 계속 하게 만들었던 문제 근데 이분탐색으로 푸는게 맞다..다른 방법이 있을수도 있겠지만 전혀 생각나지 않는다..ㅋㅋ 이 문제는 랜선자르기 [백준] 파이썬 1654 : 랜선 자르기 https://www.acm..

백준 2805 나무 자르기

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 📌 해결순서 문제에서 요구하는 값이 절단기 높이의 최댓값이므로 조건을 만족하는 절단기의 높이를 작은값부터 최댓값이 될때까지 키워나가면 된다. 절단기의 높이가 높아질수록 상근이가 가져갈수 있는 나무는 적어진다 start = 0 / end = max(lst) 1. 절단기의 높이가 너무 짧은 경우 -> 이 경우에는 상근이가 가져가려는 나무의 길이보다 더 많은 나무..

백준 1654 랜선 자르기

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 📌 해결순서 예제에서 총 11개의 랜선이 필요하므로 802 // 200 = 4 743 // 200 = 3 457 // 200 = 2 539 // 200 = 2 자르는 랜선의 길이를 200으로 설정하면 11개의 랜선이 나온다 길이가 201이라면 10개의 랜선이 나오므로 200이 문제에서 물어보는 랜선의 길이 최댓값임을 알수 있다. 1. 이분탐색의 시작과 끝을 정한다 ->..

백준 1920 수 찾기

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 📌 해결순서 이분탐색을 활용하는 문제중 가장 기본적인 문제라고 할 수 있다. 일단, 이분탐색은 데이터가 정렬 되어 있다고 가정하고 탐색을 시작한다. 다음과 같은 배열에서 2를 찾는 과정을 생각해보자 4 1 5 2 3 배열을 정렬 해준다, 1 2 3 4 5 1. 찾는 데이터가 배열에 있는 경우 target : 2 start : 0 / end : 4 비..