문제
N개의 아파트가 나란히 있고, Stations에는 기지국이 설치되어 있는 아파트 번호가 담겨져 있으며, W는 각각의 기지국이 얼마만큼의 범위를 커버할 수 있는지를 의미한다.
즉, N = 11, Stations = [4,11], W=1 과 같이 주여졌다면, 1번 아파트,2번 아파트......11번 아파트가 나란히 있고, 4번 아파트와 11번 아파트에 기지국이 설치되었다는 것이다. 이 경우, 범위가 1이기 때문에 4번 양 옆인 3,5번 아파트, 그리고 11번의 옆인 10번 아파트가 커버가 된다는 것이다..
이 경우 새로 기지국을 설치하려 할 때 가장 최소로 기지국을 설치하는 경우의 최적해를 구하는 것이 목표
어떻게 풀었지? & 어디서 헤맸지?
근래에 삽질을 가장 많이 한 문제인듯...? 어마어마한 삽질의 향연...
일단 그냥 별 생각없이 재귀 dfs로 풀려고 했다. 일단 길이랑 statations를 받았으니까 visited 배열을 만들고, 설치가 되어있으면 1, 안되어있으면 0을 만들었다. 그리고 처음 인덱스부터 기지국이 설치되어 있으면 인덱스 증가하고 재귀, 만약 기지국이 설치가 안되어 있다면 여기에 설치 하는경우/안 설치하는 경우의 재귀로.
근데 N이 200,000,000이라 당연히 시간초과... & 정확도 테스트에서는 1개가 틀린다..그니까 잘못 쓴 코드
# 오답입니다!!!
from copy import deepcopy
min_val = float("inf")
def dfs(n,stations,w,visited,start) :
global min_val
if start >= n :
if sum(visited) == n :
min_val = min(min_val, len(stations))
return
if visited[start] == 1 :
dfs(n,stations,w,visited,start+1)
else :
v = deepcopy(visited)
st = deepcopy(stations)
st.append(start+1)
for i in range(w+1) :
if start-i > 0 :
v[start-i] = 1
if start+i < n:
v[start+i] = 1
dfs(n,st,w,v,start+1+w)
dfs(n,stations,w,visited, start+1)
def solution(n, stations, w):
global min_val
visited = [0 for _ in range(n)]
for s in stations :
for i in range(w+1) :
if s-i-1 >= 0 :
visited[s-i-1] = 1
if s+i-1 < n :
visited[s+i-1] = 1
dfs(n,stations,w,visited,0)
answer = min_val - len(stations)
return answer
요새 맨날 완전탐색만 풀다보니까 그렇게 풀어진 것 같다. 그래서 약간 이진탐색 느낌으로 채워나가면 좋지 않을까 싶어 그렇게 몇시간을 더 삽질... 나중에 찾아보니까 이진 탐색 느낌으로 푸신 분들도 많았던 것 같다..ㅠㅠ 어디가 잘못이었지..
결국 처음부터 다시 생각해본 결과 풀 수 있었다.
Code
def solution(n, stations, w):
answer = 0
stations_idx = 0
location = 1
count = 0
while location <= n :
if stations_idx < len(stations) and stations[stations_idx]-w <= location <= stations[stations_idx]+w :
location = stations[stations_idx]+w+1
stations_idx +=1
else :
print(location)
location += 2*w+1
answer+=1
return answer물론 이것도 딱히 잘 짠것 같지는 않지만 일단 통과는 했으니..
그냥 간단하게 생각해서 만약 현재 위치가 주어진 기지국의 범위 안이라면 해당 범위의 맨 끝 다음 칸으로 이동 & 기지국 인덱스 증가
만약 그 범위가 아니라면 2*w+1 (내 위치에다 기지국을 세운다면 내 오른쪽으로 w칸 영향 + 다음 기지국이 왼쪽으로 w칸 영향을 줘야 최적해겠지?)
처음에 stations_idx가 stations를 벗어나는 경우를 따로 처리하려고 하다가 오히려 코드가 더 복잡해져가지고 다시 생각해보니까 그냥 이렇게만 쓰는게 훨씬 깔끔했었다... 시간복잡도도 결국 O(n)일테고....이것도 약간 그리디인가...? 모르겠네..
