백준 2300 기지국

https://www.acmicpc.net/problem/2300

DP 문제를 너무 팀원에게 맡기는 것 같아서 쉬운 DP문제를 하나 풀었습니다. 코드 최적화가 익숙해지면 쉬운 문제지만 아니라면 조금 막힐수도 있습니다.

$ O(N^2) $ 의 풀이로 풀 수 있습니다. 1번-n번 기지국의 설치 비용은 1번-i번의 설치 비용+(i+1번-n번 설치 비용) 중 최솟값과 같기 때문입니다.

i+1번-n번 기지국의 설치 비용을 계산하는 복잡도가 $ O(1) $ 임에 유의합시다. 설치 비용은 i+1번-n번 기지국에서 x좌표의 차이 또는 해당 구간에서 가장 큰 y좌표의 절대값 * 2 중 하나인데 둘 다 $ O(1) $ 에 구할 수 있습니다.

#include<bits/stdc++.h>
#define ff first
#define ss second
#define INF (int)1e9+5
using namespace std;
typedef pair<int,int> pii;
const int SZ=10005;
int memo[SZ];
pii arr[SZ];
int dp(int n){
   if(n==0) return 0;
   if(memo[n]!=-1) return memo[n];
   int mn=INF;
   int mxy=0;
   for(int i=n;i>=1;i--){
      mxy=max(mxy,abs(arr[i].ss));
      mn=min(mn,dp(i-1)+max(arr[n].ff-arr[i].ff,2*mxy));
   }
   return memo[n]=mn;
}
int main(void){
   ios_base::sync_with_stdio(false); cin.tie(NULL);
   memset(memo,-1,sizeof(memo));
   int n; cin>>n;
   for(int i=1;i<=n;i++){
      int x,y; cin>>x>>y;
      arr[i]={x,y};
   }
   sort(arr+1,arr+n+1);
   cout<<dp(n);
   return 0;
}