링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12979#
문제 설명
4G 기지국을 5G 기지국으로 모두 바꿀 예정입니다. 하지만 5G 기지국이 4G 기지국보다 전달 범위가 좁아, 어떤 아파트에는 전파가 도달하지 않는 문제가 생겼습니다.
쭉 늘어서있는 아파트 개수 n개와 기존 4G 기지국 위치가 담겨있는 배열 stations, 5G 기지국의 전파 전달 범위 w가 주어질 때, 모든 아파트에 전파를 전달하기 위한 최소 추가 5G 기지국 개수를 구하시오.
N : 2억 이하의 자연수
stations : 1만 이하의 자연수. 오름차 순으로 정렬되어 있습니다.
W : 1만 이하의 자연수
아이디어
● 아파트가 최대 2억이기 때문에 기지국에 초점을 맞춰 문제 풀이해야 할 것 같습니다.
● 기지국이 없는 구역을 구해 해당 구역에 기지국이 몇개 들어가는지 확인해서 더합니다.
● 1에서 시작해 n까지 아파트가 있어서 기지국이 사이사이 기지국 없는 구역을 구할 때 숫자에 조심해야할 것 같습니다...
코드
#include <bits/stdc++.h>
using namespace std;
int CreateStation(int betweenArea, int w)
{
if(betweenArea <= 0) return 0;
int ret = betweenArea / w ;
if((betweenArea % w) != 0) ++ret;
return ret;
}
int solution(int n, vector<int> stations, int w)
{
int answer = 0;
for(int i = 1; i < stations.size(); ++i)
{
int prevStation = stations[i-1];
int curStation = stations[i];
int betweenArea = (curStation - w -(prevStation + w) - 1);
answer += CreateStation(betweenArea, w*2+1);
}
answer += CreateStation((stations.front() - w - 1), w*2+1);
answer += CreateStation(n - (stations.back() + w), w*2+1);
return answer;
}
메모리 3.96MB, 시간 0.12ms
'알고리즘' 카테고리의 다른 글
백준(5430) - AC (0) | 2024.06.14 |
---|---|
백준(15922) - 아우으 우아으이야!! (0) | 2024.06.04 |
프로그래머스 - 파일명 정리 (0) | 2024.05.28 |
프로그래머스 - 방문길이 (0) | 2024.05.27 |
프로그래머스 - [1차]캐시 (0) | 2024.05.27 |