[백준/JAVA] 2315번 가로등 끄기

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

2315번: 가로등 끄기

 

문제

문제 유형

다이나믹 프로그래밍, 누적 합

문제 분석

실력과 기술이 좋지않으면 잡무나 평생하게 된다는 철학을 담은 문제다.

마징가z가 특정 위치(가로등) 에서 시작하고, 모든 가로등을 끌 때 까지 소모되는 전력양을 구하는 문제이다. 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P2315 {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, m;
	static int[] loc, sum;
	static long[][][] dp = new long[1005][1005][2];

	static void init() throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		loc = new int[n + 1];
		sum = new int[n + 1];
		for (int i = 1; i <= n; ++i) {
			st = new StringTokenizer(br.readLine());
			loc[i] = Integer.parseInt(st.nextToken());
			sum[i] = sum[i - 1] + Integer.parseInt(st.nextToken());
		}
		for (int i = 0; i < 1005; ++i) {
			for (int j = 0; j < 1005; ++j) {
				dp[i][j][0] = -1;
				dp[i][j][1] = -1;
			}
		}
	}

	static long solve(int left, int right, int isLeft) {

		if (left == 1 && right == n) {
			return 0;
		}

		if (dp[left][right][isLeft] != -1) {
			return dp[left][right][isLeft];
		}

		int curLoc = isLeft == 0 ? left : right;
		long result = Long.MAX_VALUE;
		if (left > 1) {
			result = solve(left - 1, right, 0) + (long) (loc[curLoc] - loc[left - 1]) *
				(sum[n] - sum[right] + sum[left - 1]);
		}
		if (right < n) {
			result = Math.min(
				result,
				solve(left, right + 1, 1) + (long) (loc[right + 1] - loc[curLoc]) *
					(sum[n] - sum[right] + sum[left - 1])
			);
		}
		dp[left][right][isLeft] = result;
		return result;
	}

	public static void main(String[] args) throws IOException {
		init();
		System.out.println(solve(m, m, 0));
	}
}

 

 

문제해석

우선 마징가z에게 가로등을 끄는 시간은 매우 작다 라고 했으니, 마징가z가 어떠한 가로등을 지나치는데 안끄고 지났을때 더 좋은 전력 소비량이 나올 가능성이 없다는 얘기이다.

따라서 i번째 가로등과 j번째 가로등이 꺼져있다면 그 사이에 있는 가로등은 무조건 불을 끄는게 이득이라는 소리이다.

 

dp배열을 3차원으로 선언한 뒤 i~j까지의 가로등이 꺼져있다를 표현하기위해 dp[i][j]를 사용하고, 

현재 마징가z가 왼쪽에 있는지, 오른쪽에 있는지를 표시하기위해 [k]까지 사용하여 3차원 배열을 사용하였다. 

현재 내 위치를 curLoc 이라고 하고, i~j번째 가로등이 꺼져있다고 가정하면 다음으로 마징가 z가 갈 수 있는 위치는 

i-1, 혹은 j+1위치를 갈 수 있을것이다. 그래서 i-1번째 위치와 j+1번째 위치를 방문한다. 

한번 이동때마다 하나의 가로등을 끄게 되는데 이 가로등이 1초에 소비되는 전력양을 누적합으로 구해놓는다면 O(1)에 초당 소비되는 전력량을 구할 수 있기 때문에 TLE를 피할 수 있게 된다.