Life Engineering
[프로그래머스] 기지국 설치 (Java) 본문
https://programmers.co.kr/learn/courses/30/lessons/12979
import java.util.*;
class Solution {
public int solution(int n, int[] stations, int w) {
int answer = 0;
int dist=(2*w)+1;
int s=1;
int start=0, end=0;
for (int i=0; i<stations.length; i++){
start=stations[i]-w<0?0:stations[i]-w;
end=stations[i]+w>n?n:stations[i]+w;
int len=start-s;
if (len>0){
if (len%dist==0){
answer+=len/dist;
}
else{
answer+=(len/dist)+1;
}
}
s=end+1;
}
if (n>end){
answer+=((n-end)%dist==0 ? (n-end)/dist : (n-end)/dist+1);
}
return answer;
}
}
그리디 문제.
기지국이 커버하는 범위를 구해준 뒤, 그 범위 사이사이의 길이에 대해 커버할 수 있는 집의 수로 나눠준다.
나머지가 0으로 떨어지면=> 그 몫을 취하고, 0으로 떨어지지 않으면 몫+1 해준다.
범위 사이사이의 길이는 i번째 기지국이 커버하는 범위의 끝+1 부터, i+1번째 기지국이 커버하는 범위의 시작-1 까지의 길이를 구해주면 된다.
다른 분(https://minnnne.tistory.com/46)의 코드를 보니,
기지국이 겹쳐있을 경우 start 지점을 끝+1로 놓는다.
'Problem Solving' 카테고리의 다른 글
[BOJ 2638] 치즈 (Java) (0) | 2022.03.17 |
---|---|
[프로그래머스] 이중 우선순위 큐 (Java) (0) | 2022.03.17 |
[BOJ 9935] 문자열 폭발 (Java) (0) | 2022.03.16 |
[프로그래머스] 경주로 건설 (Java) (0) | 2022.03.16 |
[프로그래머스] n진수 게임 (Java) (0) | 2022.03.15 |