문제보기
상당히 오래 걸렸다.
백준강의 자료를 참고해서 완성할 수 있었다.
마징가는 태권V덕분에 가로등만 끄면 되는 편한일(?)을 맡았다는 내용,
마징가의 움직임에 살펴보자 마징가는 현재 '5'번의 위치하고 있다.
그리고 끄려면 수평으로 움직여야 한다.
그렇다면 어떻게 움직일 수 있는가 ?
좌우로 움직이면 된다.
그리고 생각해보면 만약 두칸을 움직여서 끄면 건너뛴 가로등을 다시 꺼야되는
일이 발생한다.
두번 일하지 말고, 가면서 만나는 가로등은 다 끄도록하자.
결국
좌우로 움직이게 되고 가로등을 끄면서 켜져있는 값들을 더하면서 나가면된다.
점화식은
if(left - 1 >= 1) {
ans = Math.min(ans, solution(left-1,right,0) + (a[now]-a[left-1])*(s[n]-s[right]+s[left-1]));
}
if(right + 1 <=n) {
ans = Math.min(ans, solution(left,right+1,1) + (a[right+1]-a[now])*(s[n]-s[right]+s[left-1]));
}
이렇게 된다 왼쪽으로 움직이는 경우 마지막 index 1번까지 갈 수 있고 ,
오른쪽으로 움직이는 경우 마지막은 n까지 갈 수 있다.
그리고 왼쪽으로 움직인경우 index를 이동해야하기 때문에 left-1, 오른쪽은 right+1하면서 이동하면된다.
베이스 케이스는
if(left == 1 && right == n) {
return 0;
}
이렇게 된다.
그리고 현재 켜져있는 값들을 계산해야된다.
(a[now]-a[left-1])*(s[n]-s[right]+s[left-1]));
-> 끄러 이동하는 시간 // -> 그때까지 켜져 잇는 가로등의 값들 ( 시그마 형식 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | package Problems; import java.util.Arrays; /** * * 백준 2315 가로등끄기 * * 동적계획 * * */ import java.util.Scanner; public class Boj2315dp { public static int n,m; public static int a[] = new int[1001]; public static int w[] = new int[1001]; public static int s[] = new int[1001]; public static int d[][][] = new int[1001][1001][2]; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); m= in.nextInt(); for(int i = 1; i <= n; i++) { a[i] = in.nextInt(); w[i] = in.nextInt(); s[i] = s[i-1] + w[i]; } for(int i = 0; i < 1001; i++) { for(int j = 0; j < 1001;j++) { for (int w = 0; w <2; w++) { d[i][j][w] = -1; } } } System.out.println(solution(m,m,0)); } public static int solution(int left, int right, int where) { if(left == 1 && right == n) { return 0; } if(d[left][right][where] != -1) { return d[left][right][where]; } int ans = 214748364; int now = where == 0 ? left : right; System.out.println("now : " + now); if(left - 1 >= 1) { ans = Math.min(ans, solution(left-1,right,0) + (a[now]-a[left-1])*(s[n]-s[right]+s[left-1])); } if(right + 1 <=n) { ans = Math.min(ans, solution(left,right+1,1) + (a[right+1]-a[now])*(s[n]-s[right]+s[left-1])); } d[left][right][where] = ans; return ans; } } | cs |