Boj 2315 c++ 가로등 끄기

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

 

 

문제 

 

수직선 상에서의 시작 위치와 각 가로등의 위치, 각 가로등의 1초당 전력 소비량에 대한 정보가 주어졌을 때 모든 가로등을 껐을 때 누적 전력 소비량의 최솟값을 구하시오. (단, 좌표평면 상에서 1만큼 움직일때 걸리는 시간은 1초이다)

 

가로등의 개수  N  ( 1 <= N <= 1000 )

시작 위치 M ( 1 <= M <= 1000 )

 

 

관찰

 

각 가로등을 끄는 순서는 다를 수 있지만, 전력소비량을 최소화하기 위해서는 i개의 가로등을 끄는 경우에는 반드시 연속한 i개의 구간에서 꺼야한다는 것을 알 수 있다. 하지만 순서가 여러가지로 나뉠 수 있는 이유는 인접한 가로등을 끌지, 현재 구간의 반대편에 켜져있는 가로등을 끌지 결정해야 하기 때문이다.

 

즉, 구간 초당 전력소비량 합과 현재 위치에서 다음에 끌 가로등 까지의 위치를 고려해서 더욱 작은 경우만 취하면 된다.

 

 

 

구현 

 

가로등의 번호가 i 일때 가로등의 좌표를 light[i], 전력소비량을 cost[i] 라고 하자.

그리고 dp 배열의 정의는 

" dp[i][j] = 가로등을 i개 껐고, 현재 서있는 가로등의 번호가  j 일 때, 최소 누적 전력 소비량 "  으로 하겠다.

 

점화식은 현재 위치가 시작 가로등을 기준으로 오른쪽에 있는지 왼쪽에 있는지에 따라 분기하는 형태이다.

가로등을 끈 모양은 반드시 시작점 부터 이어지는 길이가 i 인 구간이기에

M을 기준으로 위치가 왼쪽일 경우에는 j 부터 j + i -1 번까지,

오른쪽일 경우는 j - i + 1 부터 j까지 "꺼짐" 처리 하면 된다.

 

불가능한 경우에 대해서는 min으로 걸러지기 때문에 구간의 모양이 불가능한 경우도 예외처리해줄 필요 없다.

 

N 제한이 1000 이기 때문에 O(N^2) 으로 작은 값 부터 채워주면 끝난다.

 

최종점화식은 다음과 같다.

 

 

    for(int i = 2; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            if(j < M  && i + j - 1 <= N) {
                dp[i][j] = min(dp[i-1][j+1] + (sum[N] - (sum[i+j-1] - sum[j])) * (light[j+1] - light[j]), dp[i-1][i+j-1] + (sum[N] - (sum[i+j-1] - sum[j])) * (light[i+j-1] - light[j]));
            }
            else if(j > M && j - i + 1 >= 1) {
                dp[i][j] = min(dp[i-1][j-1] + (sum[N] - (sum[j-1] - sum[j-i])) * (light[j] - light[j-1]), dp[i-1][j-i+1] + (sum[N] - (sum[j-1] - sum[j-i])) * (light[j] - light[j-i+1]));
            }
        }
    }

 

 

 

정답코드

 

#include <iostream>
#define inf 1000000001
using namespace std;

int dp[1001][1001], light[1001], cost[1001], sum[1001]; /*
 가로등을 i개 껐고  가로등 번호가 j일때 최소 전력 소비량
 */

int main() {

    int N, M;

    for(int i = 0; i <= 1000; i++) {
        for(int j = 0; j <= 1000; j++) {
            dp[i][j] = inf;
        }
    }

    cin >> N >> M;

    for(int i = 1; i <= N; i++) {
        cin >> light[i] >> cost[i];
        sum[i] = sum[i-1] + cost[i];
    }

    dp[1][M] = 0;

    for(int i = 2; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            if(j < M  && i + j - 1 <= N) {
                dp[i][j] = min(dp[i-1][j+1] + (sum[N] - (sum[i+j-1] - sum[j])) * (light[j+1] - light[j]), dp[i-1][i+j-1] + (sum[N] - (sum[i+j-1] - sum[j])) * (light[i+j-1] - light[j]));
            }
            else if(j > M && j - i + 1 >= 1) {
                dp[i][j] = min(dp[i-1][j-1] + (sum[N] - (sum[j-1] - sum[j-i])) * (light[j] - light[j-1]), dp[i-1][j-i+1] + (sum[N] - (sum[j-1] - sum[j-i])) * (light[j] - light[j-i+1]));
            }
        }
    }
    int ans = inf;

    for(int i = 1; i <= N; i++) {
        ans = min(ans, dp[N][i]);
    }
    cout << ans;
}