문제보기


상당히 오래 걸렸다. 

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


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

문제보기


실제로 이 문제를 푸는 방법은 여러가지가 있더라 , 

하지만 배열을 다루는 것에 있어 미숙한점을 알고 있기때문에

조건을 배열로 바꾸어 5차원 배열로 풀어보았다. 

 

풀이는 간단하지만 복잡하다. 

경우를 충분히 나누면 풀 수 있다. 

다만 그 경우가 다른 쉬운 다이나믹 문제보다 조건이 많아 처음에는

힘들었다. 


조건의 예를 들어보자 

점화식을 설명해보자면 

D[현재몇일][오늘의 출결][어제의 출결][그제의 출결][지각횟수]

이다. 

오늘 출결했다고 하면 뭘해도 상관없다.  이런식으로 조건을 나열하여 풀면된다. 

처음에는 상당히 시간이 걸렸다.

D[i][0][prev][prev2][0] += D[i-1][prev][prev2][prev3][0];

D[i][0][prev][prev2][1] += D[i-1][prev][prev2][prev3][1];


그리고 안되는 조건을 살펴보자면 

now , prev , prev2가 다 결석이면 안된다. 연속3일 결석을 할 수 가 없다. 

지각은 한번까지 허용된다. 그럼으로 오늘지각을 했다면 어제까지 지각을 하면안된다. 


주석을 달아놨으니 참고하면된다.




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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package Problems;
 
/**
 * 
 * 
 * 백준 1563 개근상
 * 
 * 동적계획
 *
 */
import java.util.Scanner;
 
public class boj1563dp {
    public static int mod = 1000000;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][][][][] D = new int[1001][3][3][3][2];
 
        for (int now = 0; now < 3; now++) {
            for (int prev = 0; prev < 3; prev++) {
                for (int prev2 = 0; prev2 < 3; prev2++) {
 
                    // 결석 연속3번은 안
                    if (now == 1 && prev == 1 && prev2 == 1) {
                        continue;
                    }
 
                    // 지각 2번은 안됨
                    if ((now == 2 && prev == 2) || (now == 2 && prev2 == 2) || (prev == 2 && prev2 == 2)) {
                        continue;
                    }
 
                    if (now == 2 || prev == 2 || prev2 == 2) {
                        D[3][now][prev][prev2][1] = 1;
                    } else {
 
                        D[3][now][prev][prev2][0] = 1;
 
                    }
 
                }
            }
        }
 
        for (int i = 4; i <= n; i++) {
            for (int prev = 0; prev < 3; prev++) {
                for (int prev2 = 0; prev2 < 3; prev2++) {
                    for (int prev3 = 0; prev3 < 3; prev3++) {
 
                        // 출석했을
                        D[i][0][prev][prev2][0] += D[i - 1][prev][prev2][prev3][0];
                        D[i][0][prev][prev2][0] %= mod;
                        D[i][0][prev][prev2][1] += D[i - 1][prev][prev2][prev3][1];
                        D[i][0][prev][prev2][1] %= mod;
 
                        // 결석
 
                        if (prev == 1 && prev2 == 1) {
 
                        } else {
 
                            D[i][1][prev][prev2][0] += D[i - 1][prev][prev2][prev3][0];
                            D[i][1][prev][prev2][0] %= mod;
                            D[i][1][prev][prev2][1] += D[i - 1][prev][prev2][prev3][1];
                            D[i][1][prev][prev2][1] %= mod;
 
                        }
 
                        D[i][2][prev][prev2][1] += D[i - 1][prev][prev2][prev3][0];
                        D[i][2][prev][prev2][1] %= mod;
 
                    }
                }
            }
        }
        
        int ans = 0;
        
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++){
                for(int k = 0; k < 3; k++) {
                    for(int l = 0; l < 2; l++) {
                        ans += D[n][i][j][k][l];
                        ans%=mod;
                    }
                }
            }
        }
        
        System.out.println(ans);
 
    }
 
}
 
cs


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

[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1495 기타리스트  (0) 2017.11.13
백준 11048 이동하기  (0) 2017.11.08
백준 1912 연속합  (0) 2017.11.07

일단 나의 하반기 계획과는 다른 방향으로 흘러갔다.

조금은 자소서를 준비했지만, 결국엔 많은 서탈을 경험하였고,

많은 시험을 봤지만, 많은 탈락을 맛봤다. 

어느순간 멘탈이 흔들렸다. 그런데 그게 지금까지도 계속 흔들리는 것 같다. 

결정적인 계기는 00회사의 시험이였다. 나는 그 시험에서 정확도 체크를 계산하여 6개중 5개 푸는 것을 목표로 했고

5개를 풀었다. 완벽했다. 장담한다. 


하지만..


탈락했다. 비록 서류 + 시험 + @로 평가하는 단계였지만, 

엄청난 멘붕이 왔다. 그날 소식듣고 독서실에서 확인하자마자

집에 갔다. 

실제로 코딩시험을 통과한 곳들도 있었다. 

하지만 코딩 시험이든 그 다음 시험이든, 나는 멘탈 유지하는 것을 실패했다. 

왜그러는지 모르겠다. 

시험전에는 계속 화장실을 가고, 손이 떨린다. 

공부를 더 많이 해서 그런가...?

시험을 보는 내내 멘탈유지가 쉽지 않더라, 어렸을때부터 시험 시간동안 세웠던 계획이 틀어지면 

뭔가 초조해지고 그랬다. 

예를들어 이번에 어떤 시험을 보면서 분명 아는문제고 풀줄아는데, 오류가나고 중간에 잠깐 막히더라, 

시간이 너무나 빠르게 흘러갔고, 그때부터 땀이 나더라.. 이게 너무 반복되었다. 

실제로 끝내고 다시 문제를 보면 쉬웠다. 왜 못풀었는지 모르겠다. 

이렇게 나의 하반기가 점점 마무리가 되어간다. 

아직 일정이 더 남았지만, 주말부터 뭔가 

가슴 한 구석이 '쿵'했다.


그래도..


날 믿기로 했다. 시간이 좀 더 걸리더라도..

'좋은 개발자'가 되기 위해서..

 

+ Recent posts

티스토리툴바