문제보기


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

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

조건을 배열로 바꾸어 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개를 풀었다. 완벽했다. 장담한다. 


하지만..


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

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

집에 갔다. 

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

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

왜그러는지 모르겠다. 

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

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

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

뭔가 초조해지고 그랬다. 

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

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

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

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

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

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


그래도..


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

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

 

문제보기


*경우는 두 가지가 있습니다. (더하기 , 뺴기)

*조건에 따라서 필터링 해줍니다 (0보다 커야됩니다.)

*2차원으로 만들어 값을 체크하면서 진행합니다. 

 -> D[N][M]    

*곡 연주가 가능하다면 배열의 해당칸에 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
package Problems;
 
/**
 * 
 * 백준 1495 dp
 *
 */
import java.util.Scanner;
 
public class Boj1495dp {
 
    public static int n, s, m;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        s = in.nextInt();
        m = in.nextInt();
        int max = -1;
        int[][] arr = new int[n + 1][m + 1];
 
        int[] v = new int[n + 1];
 
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
        }
        arr[0][s] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (arr[i-1][j] == 1) {
                    if (j + v[i] > m && j - v[i] < 0) {
                        continue;
                    }
 
                    if (j + v[i] <= m) {
                        arr[i][j + v[i]] = 1;
                    }
 
                    if (j - v[i] >= 0) {
                        arr[i][j - v[i]] = 1;
 
                    }
 
                }
 
            }
        }
 
        int result = -1;
        for (int j = 0; j <= m; j++) {
            if (arr[n][j] == 1) {
                if (result < j) {
                    result = j;
                }
            }
        }
 
        System.out.println(result);
 
    }
 
}
 
cs


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

백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 11048 이동하기  (0) 2017.11.08
백준 1912 연속합  (0) 2017.11.07
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07

+ Recent posts

티스토리툴바