공부하고 기록하는, 경제학과 출신 개발자의 노트

프로그래밍/코딩테스트 문제풀이

[Python] 프로그래머스. 기지국 설치 (Level 3)

inspirit941 2019. 11. 7. 19:58

https://programmers.co.kr/learn/courses/30/lessons/12979

 

코딩테스트 연습 - 기지국 설치 | 프로그래머스

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다. 예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g

programmers.co.kr

N 크기가 크길래 이분탐색으로 풀어야 하나 고민했지만, 문제를 푸는 데 핵심값은 stations이었고, 10,000 이하라서 조건대로 풀면 쉽게 풀 수 있는 문제.

'최소로 설치하는 방법' = 전파가 닿지 않는 거리 / (기지국 위치 + 전파가 닿을 거리 * 2) 값을 올림하면 된다.

ex) 전파가 닿지 않는 거리가 6, 전파 거리 2일 경우

기지국 하나 설치 시 커버하는 범위는 2 * 전파 거리 + 기지국 설치위치 (1) = 2  * 2 + 1로 5이다.

따라서 6의 거리를 커버하면 기지국 2개가 필요하며, 이는 6 / 5를 올림한 값이다.