수학3 [백준] 2805 - 나무 자르기(Python) 문제 출처: www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 풀이: 이분탐색 문제이다. 아마도 이분 탐색인 문제를 파악하지 못하고 푼다면 시간초과를 마주하게 될 것이다. 필자는 아무리 생각해보아도 이분 탐색이 어떻게 적용되는지 모르겠어서 질문 게시판을 참조햇다 자르려는 높이를 x라고 하면, 그 때 잘라내는 나무의 양을 O(N)에 구할 수 있습니다. x가 작을 수록 나무의 양이 같거나 많아지는 것이 자명하므로, 높이.. 2021. 4. 2. [백준] 2869 - 달팽이는 올라가고 싶다 (Python) 문제 출처 : www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 문제 풀이: 이 문제를 쉽게 생각하고 while문을 돌리면 무조건 시간초과가 난다. 입력값의 최대값이 1,000,000,000 이기 때문에) 이 문제에서 체크해야하는 부분은 "또, 정상에 올라간 후에는 미끄러지지 않는다." 라는 부분이다. 때문에 원하는 높이에 다 올라간 낮을 정답으로 출력해야 한다. 이를 수학적으로 표현하면 V_d (day 만큼 지났을때 있는 높이 ) = a * d - b * (d-1) 이를 d에 대해서 정리하면 day = v-b / a.. 2021. 4. 2. [백준] 2217 - 로프 (Python) 문제 출처 : www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 풀이 : 최대무게를 걸어야하고 , "몇 개"의 로프만 골라서 사용할 수 있다. 로프를 여러개 사용하는게 무게가 줄어들어서 좋을까? 라는 생각이 들 수 있지만 주의해야하는 것은 로프마다 견딜 수 있는 무게가 다르다는 점이다. 이런 점을 보았을때 로프를 내림차순으로 정렬 시킨후 모든 로프에 대해서 무게를 늘려가며 최대값을 갱신해주면된다. 제일 무거운 무게를 지탱할 수 있는 로프 순서대로.. 2021. 3. 30. 이전 1 다음 반응형
