문제보기


상당히 오래 걸렸다. 

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


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

문제보기


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

*조건에 따라서 필터링 해줍니다 (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

2017.11.02 ** 목요일 ** Solution - 1699(제곱수의 합)
백준 1699 제곱수의합

풀이방법: 동적계획법

엄청 시간이 걸렸던 문제다.

처음에 생각했던 것은 d[2-1] = d[1]+1.. 이런식으로 했었다.

그런데 여기서 4=2의 제곱이 되니 카운트가 바껴야 하는데 그 포인트를 못구했다.

그래서 중간에 월드시리즈 7차전을 잠깐보고 다시 문제를 풀었다.

오늘따라 다저스 타자들이 힘이 없어 보였다..나처럼 ㅜ

풀이방식

한번 생각해보자 ,

처음에 생각했던 방식 d[N - (N-1)] = d[N-1]+1 에 대해서 한번더 생각해보았다.

이렇게 하다보면 d[4]일때가 1차적으로 문제가 생기는데 ,

d[4-4] = d[0]+1을 만들어 줘야하기 때문이다.

자세히 식을 들여다보니 4 =2*2 가 된다. 그렇다면 1은 1x1이 된다는 것을 알 수 있다.

이제 반복문에 대해서 생각을 해보았다.

먼저 우리는 동적계획법을 할꺼고 bottom-up 방식을 사용하기 때문에 1부터 n까지 계산을

해줘야 된다.

for(int i = 1; i < n+1; i++) 로 시작하여

for(int j = 1l; j*j<i; j++)를 만든다. jxj < i 가 포인트인데 이유는

이렇게 하면 2의 제곱은 4부터 등장하게 되고, 처음 방식을 하면서 문제였었던 8은

d[8-4] = d[4] +1 = d[0] +1 +1 = 2가 될 수 있다.

따라서 조건에 의해 제곱수의 범위를 잘 나눌 수 있다. (손으로 해보는 것을 추천한다.)

점화식은 간단하다.

d[i] = Math.min(d[i],d[i-j*j]+1)

여기서 답을 놓칠뻔했다.

왜냐하면 d[i]를 초기화 해주지 않았다. d[i]의 초기화는 모두 d[i]=i로 해야된다.

이유는 모든 수는 1의 제곱으로 구성되어있기때문에, 1의 개수가 최대 개수가 된다.
코드 전체 보기

: 알고리즘은 항상 어렵다.

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

백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03
백준 11051 이항 계수2  (0) 2017.11.01
백준 1915 가장 큰 정사각형  (0) 2017.11.01

+ Recent posts

티스토리툴바