문제 보기


* 몸이 안좋아서 , 짧게 하겠습니다.


4가지 풀이가 있습니다. 


solve1 은 현재칸을 기준으로 전 단계가 될 수 있는 칸들을 계산합니다.


solve2 는 현재칸을 기준으로 현재칸이 갈 수 있는 3가지의 경로를 계산합니다.


solve3는 solve1을 봤을때 대각선으로 바로 이동하는 수는 다른 방법으로 오는 수들 보다 작을 수 밖에 없습니다. 

이유는 모두 0보다 크기때문입니다. 그러기 때문에 수가 줄어들일이 없습니다. solve1 - 대각선 이라고 생각하시면 될 것 같습니다.


solve4는 재귀로 풀어봤습니다. 딱히 어려운건 없습니다.


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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package Problems;
 
/**
 * 
 * 
 * 백준 11048 이동하기 
 *  
 *
 */
import java.util.Scanner;
 
public class Boj11048dp {
 
    public static int n, m;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
 
        int[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        int[][] solve4 = new int[n + 1][m + 1];
        
        solve1(arr);
        solve2(arr);
        solve3(arr);
        int temp = solve4(arr,solve4,n,m);
        System.out.println(temp);
 
    }
 
    public static void solve1(int[][] arr) {
 
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], Math.max(dp[i - 1][j - 1], dp[i][j - 1])) + arr[i][j];
                System.out.println("arr" + arr[i][j] + "    :   dp"  + dp[i][j]);
            }
        }
 
        System.out.println(dp[n][m]);
 
    }
 
    public static void solve2(int[][] arr) {
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
 
                if ( j + 1 <=m && dp[i][j + 1] < dp[i][j] + arr[i][j + 1]) {
                    dp[i][j + 1] = dp[i][j] + arr[i][j + 1];
                }
 
                if (i + 1 <= n && j + 1 <= m && dp[i + 1][j + 1] < dp[i][j] + arr[i + 1][j + 1]) {
                    dp[i+1][j + 1] = dp[i][j] + arr[i + 1][j + 1];
                }
 
                if (i + 1 <=n && dp[i + 1][j] < dp[i][j] + arr[i + 1][j]) {
                    dp[i+1][j] = dp[i][j] + arr[i + 1][j];
                }
            }
        }
 
        System.out.println(dp[n][m]);
    }
 
    public static void solve3(int[][] arr) {
 
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
            }
        }
 
        System.out.println(dp[n][m]);
 
    }
 
    public static int solve4(int[][] arr, int[][] dp, int x, int y) {
 
        if (x == 1 && y == 1) {
            return arr[1][1];
        }
        if (x < 1 || y < 1) {
            return 0;
        }
 
        if (dp[x][y] > 0) {
            return dp[x][y];
        }
 
        dp[x][y] = solve4(arr, dp, x - 1, y) + arr[x][y];
        int temp = solve4(arr, dp, x, y - 1) + arr[x][y];
 
        if (dp[x][y] < temp) {
 
            dp[x][y] = temp;
        }
 
        return dp[x][y];
 
    }
 
}
 
cs


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

백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13
백준 1912 연속합  (0) 2017.11.07
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07

문제보기 


연속합을 구할때 유의할점은 

음수를 포함해도 답이 될때가 있다는 것이다. 

예를 들어 10 -1 11 일때, 음수를 포함하지 않으면 답이 나오질 않는다. 음수를 포함해서 10 + (-1) + 11 이 되어야만 가장 큰 연속합이된다.


D[i]는 A[i]로 끝나는 최대 연속합을 저장하는 배열이다. 


1. A[i-1]로 끝나는 연속합에 , A[i]가 포함된다. 

2. 1번의 경우보다 A[i]가 큰 경우이다. 


이 두개의 경우로 식을 세우면 된다.


D[i] = Math.max(A[i],D[i-1]+A[i])


시간복잡도는 O(N)이다. N번의 횟수와 계산식2개면 되니까! 


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
package Problems;
/**
 * 
 * 백준 1912 연속합 
 * 
 * 동적 계획
 * 
 */
import java.util.Scanner;
 
public class Boj1912dp {
    
    public static int n,arr[],dp[];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n+1];
        dp = new int[n+1];
        
        for(int i = 1; i < n+1; i++) {
            arr[i] = in.nextInt();
        }
        
        for(int i = 1; i < n+1; i++) {
            
            dp[i] = Math.max(arr[i], dp[i-1]+arr[i]);
            
        }
        
        int ans = dp[1];
        
        for(int i = 1; i < n+1; i++) {
            
            if(ans < dp[i]) {
                ans = dp[i];
            }
        }
        
        System.out.println(ans);
        
    }
 
}
 
cs


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

백준 1495 기타리스트  (0) 2017.11.13
백준 11048 이동하기  (0) 2017.11.08
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07
백준 2579 계단오르기  (0) 2017.11.07

문제보기


11053 가장 긴 증가하는 부분수열


을 참고하면 된다.


달라진 것은 하나다. 


D[i] < D[j]+1

일때 +1 의 의미는 수열의 길이가 1증가 한다는 것이다. 

여기서 +1 -> A[i]로 바꿔준다면 값들을 더하면서 증가하는 수열이 될것이다. 


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
package Problems;
 
/**
 * 
 * 백준 11055 LIS
 * 
 * 
 */
 
import java.util.Scanner;
 
public class Boj11055dp {
    public static int n, arr[], d[];
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        n = in.nextInt();
        
        arr = new int[n];
        d = new int[n];
 
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
 
        for (int i = 0; i < n; i++) {
            d[i] = arr[i];
 
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && d[i] < d[j] +arr[i]) {
 
                    d[i] = d[j] + arr[i];
 
                }
            }
 
 
        }
        
        int max = d[0];
        
        for(int i = 0; i < n; i++) {
            if(max < d[i]) {
                max = d[i];
            }
        }
        
        System.out.println(max);
 
    }
 
}
 
cs


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

백준 11048 이동하기  (0) 2017.11.08
백준 1912 연속합  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07
백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03

문제보기


부분수열 문제이다. 


그리고 동적계획법이지만 이것은 LIS풀이가 적용되었다. 

'수열 A가 주어졌을때, 가장 긴 증가하는 부분수열을 구하라'  이다.

즉, 수열마다 이게 몇번째 수열인지 최대값으로 체크한다. 

수열이 존재할때 각각의 위치의 해석은 

A[i]를 마지막으로 하는 가장 긴 증가하는 부분수열의 길이이다.


조건은 이러하다


A[i]가 있을때, i 보다 작은 index들(ex. 0~j)의 값들을 A[i]와 비교한다. 그리고 A[i]가 A[j]가 '증가하는 수열'이므로 길이를 비교한다.

조건 : j<i , A[j] < A[i] 

또 하나의 조건이 더 있다. 만약 D[i]가 4인데, D[j]가 2이면 A[j]와 A[i]가 부분수열이여도 길이를 바꿔줄 필요가 없다. 

그래서 이러한 조건이 붙는다. 


D[i] < D[j]+1


끝이다. 코드를 보면 이해가 될 것이다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
package Problems;
 
/**
 * 
 * 백준 11053 LIS
 * 
 * 
 */
 
import java.util.Scanner;
 
public class Boj11053dp {
    public static int n, arr[], d[], max = 0;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        n = in.nextInt();
 
        arr = new int[n];
        d = new int[n];
 
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
 
        for (int i = 0; i < n; i++) {
            d[i] = 1;
 
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && d[i] < d[j] + 1) {
 
                    d[i] = d[j] + 1;
 
                }
            }
 
            if (max < d[i]) {
 
                max = d[i];
            }
 
        }
        
        System.out.println(max);
 
    }
 
}
 
cs
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39



 

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

백준 1912 연속합  (0) 2017.11.07
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03


문제보기


문제를 살펴보면 이러하다.


1. 한번에 1~2계단 갈 수 있다. 

2. 연속3개는 밟을 수 없다. 

3. 그리고 밟았을때, 포도주 문제와 달리 선택/미선택의 결정을 할 수 없다. 


경우를 나눠보자 


첫 번째, 1개 연속 밟았을 경우 

i 번째 일때 , i-1을 밟지 못한다. 그리고 i-2번째를 밟고 올라온다 

-- > D[i-2]+A[i]


두 번째, 2개 연속 밟았을 경우 

i번째 일때, i-1을 밟아야한다. 하지만 i-2번을 밟으면 규칙에 위배되므로 밟지 않는다. 

그리고 D[i-3]을 더한다.(여기는 뭘해도 상관없다. 규칙에 영향을 안받음)


점화식은 아래와 같다. 

 dp[i] = Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);

2차원 배열의 경우 점화식 : D[i][1] = Math.max(D[i-2][2],D[i-2][1])+A[i]

D[i][2] = D[i-1][1] + A[i]

Math.max(D[N][1],D[N][2])

<전체코드>

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
package Problems;
/**
 * 
 * 백준 2579 계단오르기 
 * 
 * 동적계획법 
 * 
 * 
 */
import java.util.Scanner;
public class Boj2579dp {
    public static int n,arr[],dp[];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n+1];
        dp = new int[n+1];
        
        for(int i = 1; i <=n; i++) {
            
            arr[i] = in.nextInt();
        }
        
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
        for(int i = 3; i <=n; i++) {
            
            dp[i] = Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);
            
        }
        
        System.out.println(dp[n]);
    }
}
 
cs


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

백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03
백준 1699 제곱수의 합  (0) 2017.11.02

Java 9 요약 보러가기

출저: pop it의 심천보님




잘 정리가 되어있는 글을 읽고, 공유하게 되었습니다. 


이번 발표에 대한 가장 충격이었던 부분은 'var 지원'이였습니다. 뭔가 어색하네요 ,


한번 다들 읽어보셔요 ! 

'개발이야기 > Java' 카테고리의 다른 글

Linked List (단순 연결 리스트) 소스  (0) 2017.11.10
GC(가비지 콜렉션)에 대한 공부  (0) 2017.11.03

+ Recent posts

티스토리툴바