Dalin's Archive

문제 보러 가기!! 풀이🤗 이분 탐색!!! 으로 풀었다. 이분 탐색에서 구하는 값은 '총 심사하는 데 걸리는 시간' 즉 ans 이다. 최솟값은 1, 최댓값은 (가장 짧은 심시 시간 X 심사할 사람의 수)로 했다. 그 시간을 구한 뒤에, 그 시간 동안 상근이와 친구들이 모두 심사 받을 수 있는지 봤다. (calculate_screening_cnt 함수) 모두 심사받을 수 있다면 답이 될 수 있는 건데, 더 짧은 시간에 심사 받을 수도 있기 때문에 return을 하지는 않았다. 모두 심사받을 수 없다면, 이 값을 늘려줘야 한다. 코드❤️ import sys input = sys.stdin.readline N, M = map(int, input().split()) times = list(int(input())..

문제 보러 가기!! 재밌는 이분 탐색 문제였다~ 처음에 left를 0, right를 A로 삼고 이분 탐색을 시작했다. 상근이가 내는 전기 요금이 mid라고 가정하고, 아래 계산이 맞는지 봤다. 1. 상근이가 내는 전기 요금을 가지고, 상근이가 쓴 전기 사용량을 계산한다. 2. 상근이가 쓴 전기 요금에 B를 더하면 이웃이 쓴 전기 요금이 된다. 이를 가지고 이웃이 쓴 전기 사용량을 계산한다. 3. 상근이가 쓴 전기 사용량과 이웃이 쓴 전기 사용량을 합쳤을 때 내야 하는 요금을 계산한다. 4. 3번의 결과와 A를 비교한다. 4-1. 같으면 정답이다! 4-2. 3번의 결과가 A보다 더 크면, 상근이가 쓴 전기 요금(mid)을 낮추어야 한다. 4-3. 3번의 결과가 A보다 더 작으면, 상근이가 쓴 전기 요금(m..

문제로 GO !! 처음에 어떻게 풀까 하다가, 아래 '이분탐색'이라는 알고리즘 분류를 보고 힌트를 얻어서 풀었다. '블루레이 크기'를 기준으로 삼아서 이분 탐색을 했다. 블루레이 크기의 최소는 1이고(강의 수가 1개 이상이고, 기타 강의도 자연수로 주어진다고 해서) 최대는 sum(lectures)이다. 만약에 M이 1이라고 생각하면, 하나의 블루레이에 모든 강의를 담아야 하니까 그때 크기가 sum(lectures)이다. 그래서 left =1, right= sum(lectures)를 시작으로 해서, 계속 이분 탐색을 했다. mid를 구해서, 그 크기의 블루레이 M개로 강의를 모두 잘 담을 수 있는지 체크했다. (check 함수) 잘 담을 수 있으면, 일단 ans을 업데이트하고 ..

백준 2805번 문제 문제 풀이 이분 탐색을 활용해서 풀었다. 1.나무 자르는 위치가 가장 낮을 때(0) 값을 down으로, 가장 높을 때(가장 높은 나무의 높이) 값을 up으로 함. (처음에는 나무 자르는 위치가 가장 낮을 때를 가장 작은 나무 높이로 했는데, 그게 아니었다!) 2. mid를 up, down을 더하고 2로 나눈 몫으로 함. 이 위치에서 나무들을 자를 경우에 잘린 나무들의 합을 구함. 3-1. 잘린 나무들의 합이 필요한 나무 길이와 일치하는 경우: answer에 mid를 대입하고 break하기 3-2. 필요한 나무 길이보다 많은 경우: 이게 정답이 될 수도 있는 것이니까(3-1이 안될 경우에) answer에 mid를 대입함. 그리고 down을 mid+1로 바꿔서 2로 돌아감. 3-3. 필..