개발하는 개구리

🐸 문제 정보 22868번: 산책 (small) 코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다. 현재 있는 곳 $S$에서 출발하여 $S$와 다른 곳인 $E$를 찍고 다시 $S$로 돌아오는 경로로 www.acmicpc.net 🤖 알고리즘 이분탐색 ⏱️ 풀이 시간 26.22m 📝 풀이 문제를 보고 이분탐색으로 풀어야된다는 것은 알았으나... 정확한 아이디어가 떠오르지 않아 검색의 힘을 빌렸다. 처음에는 mid와 근사한 값에 공유기를 위치시키는 형태로 이분탐색을 생각했었는데, 그게 아니라 mid는 두 집 사이의 거리로 두고, 그 거리만큼 공유기를 두었을 때 비치할 수 있는 공유기의 개수로 정답을 파악하는 형식이었다. 이때 start와 end의 값을 평소처..

🐸 문제 정보 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 🤖 알고리즘 이분탐색 ⏱️ 풀이 시간 20.59 📝 풀이 간단한 조건이 추가된 이분탐색 문제였다. 크게 어려운 것 같진 않았는데 여전히 어느 상황에서 start와 end 값을 뭘로 바꾸어야하는지 헷갈린다. 사실 나무 길이를 구하는 과정 때문에 시간초과가 당연히 날거라고 생각했는데 이게 안나네...? 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n, m = ..

🐸 문제 정보 1166번: 선물 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 www.acmicpc.net 🤖 알고리즘 이분탐색 ⏱️ 풀이 시간 26.04m 📝 풀이 처음에 수학 문제라고 확신하고 풀었다. 이유는 (L / A) * (W / A) * (H / A) = N인 경우의 A 값을 찾으면 되니까... 하고 풀었으나 실패. 결국 검색의 힘을 빌렸고, 이분탐색 문제인 것을 알았다. start는 0, end는 L, W, H 중 가장 큰 값을 선택 end의 최대 값과 비교했을 때 반복문 100번 정도 돌리기 가능 (2 ^ 100) 블럭 개수는 (L ..

🐸 문제 정보 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 🤖 알고리즘 이분탐색 (이지만 나는 그리디로 풀었..다) ⏱️ 풀이 시간 10.58m 📝 풀이 유형은 이분 탐색이었지만, 문제를 봤을 때 이분탐색보다 그리디가 먼저 떠올랐다. 이분탐색 풀이도 아래에 있다. 입력 값을 오름차순으로 정렬 (현재까지 남은 값 / 남은 인원)과 현재 보고있는 값을 비교한다 만약 현재 보고 있는 값이 더 작다면, 예산 최대 값에서 현재 보고 있는 값을 빼고 res와 뺀 값을 비교한다 반대의 경우, (현재까지 남은 값 ..