23.02.28 파이썬 코딩 퀴즈#175 기지국 설치(프로그래머스 스쿨)

이번 문제는 기지국 설치 문제이다.

조건은 조금 까다롭다.

기존에 설치된 4g 기지국은 5g 기지국으로 교체가 되고 이때 전파가 도달 가능한 거리 W에 의해 전파가 닫지않는 아파트가 발생한다. 따라서 5g 기지국을 추가로 설치해야 하며, 이때 최소한으로 필요한 기지국의 수를 반환하면 된다.

주의할 조건 중 하나인 W 는 해당 위치 기준으로 양 옆의 거리를 의미한다.

제한사항을 살펴보면 N 이 2억 이하의 자연수이다. 즉 N 을 가지고 코드를 짜면 반드시 시간초과에 걸릴것 같은 느낌이 든다.

해당 문제를 풀기위해 전파가 통하지 않는 구간을 구해야 한다. 집 번호는 크게 중요하지 않다. 구간의 길이가 가장 중요하다.

 

for문을 사용해서 구간을 설정하는것에는 첫번째 집에서 첫번째 기지국, 마지막 기지국에서 마지막 집까지 거리를 설정하기 어려워 따로 if문을 통해 설정해 주었다.

그리고 구간좌표를 w*2+1 로 나눈 값을 올림하여 answer에 전달해 주면 된다.

 

한가지 염두해야 할 사실은 전파가 통하지 않는 집을 구하는 것이다.

즉 기지국이 3에 있고, w 가 1 이라면 2,3,4 집에는 전파가 통한다. 하지만 1번 집에는 여전히 전파가 통하지 않는다.

해당 수치들을 첫번째 if문에 대입해보면 3 - 1 - 1 >= 1 조건에 만족한다.

그리고 여기서의 숫자들은 index가 아닌 상수임을 염두해두면 코드를 작성할 때 어느정도 수식의 오류를 벗어날 수 있다.