내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
징검다리
ps:problems:programmers:43236
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 징검다리 ====== ===== 풀이 ===== * [[ps:problems:boj:6209]]와 동일한 문제이다. * [[ps:이진 검색#파라메트릭 서치]]로 푸는 문제. * "제거할 돌의 갯수가 n일때의 거리의 최솟값 중 최댓값=x를 구하라" 가 원래 문제인데, 이걸 파라메트릭 서치 형태로 바꾸기 위해서 f(x)를 "거리의 최솟값이 x일때 제거할 돌의 최소 갯수" 또는 "모든 거리를 x보다 크게 만들기 위해 제거해야 하는 돌의 최소갯수" 라고 정의한다. 그러면 x가 커질수록 f(x)도 커진다. 이제 풀어야 하는 문제는 "f(x) ≤ n 인 x의 최댓값을 [1, 1,000,000,000] 범위 안에서 구하라"가 된다 * n이 픽스된 상황에서 x의 범위를 구하는 문제를, 결정 문제로 바꾸는 과정에서는 x가 픽스된 상황에서 n의 범위를 체크하는 문제가 되다 보니 조금 헷갈리긴 한다. * f(x) 를 구하는 것은, 앞에서부터 이전 돌의 위치부터 현재 돌의 거리가 x보다 작으면 현재 돌을 제거하는 방식으로 그리디하게 O(m)에 구할 수 있다 (m은 돌의 갯수) * 이분탐색 구간의 상한은, distance / {남은돌의 갯수} 이다. * 따라서 총 시간 복잡도는 O(mlogn)이 된다 (n=distance) ===== 코드 ===== <dkpr py> """Solution code for "Programmers 43236. 징검다리". - Problem link: https://programmers.co.kr/learn/courses/30/lessons/43236 - Solution link: http://www.teferi.net/ps/problems/programmers/43236 """ from teflib import binsearch def solution(distance, rocks, n): def is_valid(min_dist): prev_rock = 0 removed_rock_count = 0 for rock in rocks: if rock - prev_rock >= min_dist: prev_rock = rock else: removed_rock_count += 1 if distance - prev_rock < min_dist: removed_rock_count += 1 return removed_rock_count <= n rocks.sort() beg, end = 0, distance // (len(rocks) - n + 1) + 1 return binsearch.maximum_valid_integer(beg, end, is_valid) </dkpr> * Dependency: [[:ps:teflib:binsearch#maximum_valid_integer|teflib.binsearch.maximum_valid_integer]] {{tag>프로그래머스 ps:problems:programmers:Level_4}}
ps/problems/programmers/43236.txt
· 마지막으로 수정됨: 2022/01/29 16:31 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로