문제보기


상당히 오래 걸렸다. 

백준강의 자료를 참고해서 완성할 수 있었다. 


마징가는 태권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

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 네트워크  (0) 2020.08.23
[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13
백준 11048 이동하기  (0) 2017.11.08

+ Recent posts