BAEKJOON 2315번: 가로등 끄기

[사진1]문제와 입력 조건

이 문제는 DP로 해결할 수 있다.

먼저 D[i][j][p]를 i~j까지의 가로등이 꺼져있고, p가 0일때 마징가는 i, p가 1일때 마징가는 j의 위치에 있는 상태에서 가로등 끄기를 시작했을때 낭비되는 최소한의 전력이라고 정의한다.

따라서 처음 시작위치는 M번째 가로등이므로 D[M][M][0] or D[M][M][1]의 값을 구해주면 된다.

 

수가 늘어나는 방향을 오른쪽, 그 반대방향을 왼쪽이라고 하면, 마징가가 현재위치에서 왼쪽, 오른쪽으로 이동하는 상황을 나누어 생각해주면 된다는 것을 쉽게 알 수 있다.

 

이를 생각하면

D[i][j][p]=min(D[i-1][j][0]+'이 경우 이동에 사용되는 전력', D[i][j+1][1]+'이 경우 이동에 사용되는 전력')

 

저 경우에 따른 이동에 사용되는 전력은 현재 마징가의 위치를 P, 이동해야 할 가로등의 위치를 Q 라고 하면

전력 = |P-Q|*(현재 켜져있는 가로등의 초당 전력 소비량의 합)

 

현재 상황에서 켜져있는 가로등의 초당 전력 소비량의 합은 부분합으로 구할 수 있다.

S[i]를 1~i 까지의 모든 가로등의 초당 전력 소비량의 합이라고 정의하면

(현재 켜져있는 가로등의 초당 전력 소비량의 합) = S[N]-S[j]+S[i-1]

 

시간 복잡도는 O(N×N)이다.

이를 이용해서 코드를 작성해 주면 된다.

아래에 참고할 수 있는 c++ 코드를 첨부해 두었으니 필요하면 참고하면 된다.

 

 

#include <bits/stdc++.h>
#define w (S[N]-S[j]+S[i-1])
// w는 켜져있는 가로등의 전력 소비량의 합 
#define MAX 2000000000
using namespace std;
int D[1003][1003][2],S[1003];int N,M,A[1003];
int f(int i,int j,int p){
    if(D[i][j][p])return D[i][j][p];
    int pos=p?j:i;D[i][j][p]=MAX;
    if(i>1)D[i][j][p]=f(i-1,j,0)+w*(A[pos]-A[i-1]);
    if(j<N)D[i][j][p]=min(D[i][j][p],f(i,j+1,1)+w*(A[j+1]-A[pos]));
    // i>1 일때만 왼쪽으로 이동할 수 있고, j<N 일때만 오른쪽으로 이동 가능 
    if(D[i][j][p]==MAX)D[i][j][p]=0;
    return D[i][j][p];
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++){scanf("%d%d",&A[i],&S[i]);S[i]+=S[i-1];}
    printf("%lld",f(M,M,0));
    return 0;
}