본문 바로가기

백준 문제 풀이150

[백준] 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 이 문제 역시 파라메트릭 서치 문제이다. n개의 나무들을 임의의 h값으로 잘라보면서 최적의 해를 구하는 문제이다. n=5 m=20 # 필요한 나무의 길이 array=[4, 42, 40, 26, 46] 일때 h의 값을 0~max(array)로 설정한후 이분탐색으로 잘라보며 최적의 해를 찾는다. 여기서 주의 해야할 점은 자르는 높이인 h가 나무보다 크다는 조건을.. 2021. 9. 16.
[백준] 1654번 : 랜선자르기 [파이썬] https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이 문제는 전형적인 이진탐색문제이자, 파라메트릭 서치유형의 문제이다. 파라메트릭 서치는 최적화 문제를 결정문제로 바꾸어 해결하는 기법이다. '원하는 조건을 만족하는 알맞은 값을 찾으라'는 문제에 사용하면된다. 예를 들어 범위내에 조건을 만족하는 가장 큰 값을 찾는 문제는 이진탐색으로 범위를 좁혀가며 해결 할 수있다. 이문제의 풀이 아이디어는 의외로 간단한데 정답인 최대.. 2021. 9. 16.

티스토리툴바