BOJ 2300: 기지국 [Python 3]

오늘의 문제는 Dynamic Programming으로 풀 수 있는 문제이다.

은근 잘 보일만 하면서도 각이 잘 안 보이는게 Dynamic Programming인 것 같다.

문제 자체는 이해하기 쉽다. 기지국들이 정사각형 모양으로 통신 범위를 만드는데, 모든 빌딩들이 이 통신폭 안에 있어야한다. 모든 기지국들은 x축 위에 있다.

n=int(input())
coord=[list(map(int,input().split())) for _ in range(n)]
for i in range(n):
    if coord[i][1]<0:
        coord[i][1]*=-1
coord.sort()
coord=[[-1e10,-1e10]]+coord[:]
dp=[0]*(n+1)
dp[0]=0
for i in range(1,n+1):
    dp[i]=dp[i-1]+coord[i][1]*2
    ymax=coord[i][1]*2
    for j in range(i-1,0,-1):
        ymax=max(coord[j][1]*2,ymax)
        maxlen=max(coord[i][0]-coord[j][0],ymax)
        dp[i]=min(dp[i],dp[j-1]+maxlen)
print(dp[n])

 

먼저 각 빌딩 좌표의 값을 입력받을 때, 해당 값이 y값이 음수여도, x축에 대하여 평행이동을 한다.

어차피 모든 빌딩의 좌표가 x축 위에 있기 때문에, x축과 같은 거리만큼만 떨어져 있으면 되기 때문이다.

그리고 빌딩들을 돌면서 사각형을 그리기 시작하는데,

첫 번째 빌딩일때는 당연히 빌딩의 높이만큼만 통신폭 안에 있으면 되기 때문에, 해당 빌딩의 높이를 통신폭으로 둔다.

dp에 저장한다.

 

두 번재 빌딩부터는 해당 빌딩 (A라고 하자) 이전에 있던 빌딩들을 순차적으로 하나씩 돌면서 (이때 고른 임의의 값을 B라고 하자), 

dp[A-1]와 마지막으로 들어온 A값의 통신폭의 합 

VS

dp[B-1]의 값과 B번째부터 A번째 빌딩까지 포함하는 통신폭의 합

 

을 비교한다.