BOJ::2096 내려가기

https://www.acmicpc.net/problem/2096


dp 문제이다.

먼저 자바로 풀 때

int map[100001][3];

int d[100001][3];

으로 놓고 풀어서 통과했는데, 그대로 C++로 짜니 메모리 초과가 나왔다.

그래서 생각을 조금 더 해보니 d배열을 d[2][3]으로 선언하면 충분했다.

자바코드와 C++코드의 다른점을 잘 보면 될거 같다.



<JAVA>


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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    static int n;
    static int d[][] = new int[100001][3];
    static int map[][] = new int [100001][3];
    
    public static void main(String args[]) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        
        for(int i = 1 ; i <= n ; i++){
            st = new StringTokenizer(br.readLine());
            map[i][0] = Integer.parseInt(st.nextToken());
            map[i][1] = Integer.parseInt(st.nextToken());
            map[i][2] = Integer.parseInt(st.nextToken());
        }
        
        d[1][0]=map[1][0];
        d[1][1]=map[1][1];
        d[1][2]=map[1][2];
        
        for(int i = 2 ; i <= n ; i++){
            d[i][0]=map[i][0]+Math.max(d[i-1][0], d[i-1][1]);
            d[i][1]=map[i][1]+Math.max(d[i-1][0], Math.max(d[i-1][1], d[i-1][2]));
            d[i][2]=map[i][2]+Math.max(d[i-1][1], d[i-1][2]);
        }
        int max = Math.max(d[n][0], Math.max(d[n][1], d[n][2]));
        
        for(int i = 2 ; i <= n ; i++){
            d[i][0]=map[i][0]+Math.min(d[i-1][0], d[i-1][1]);
            d[i][1]=map[i][1]+Math.min(d[i-1][0], Math.min(d[i-1][1], d[i-1][2]));
            d[i][2]=map[i][2]+Math.min(d[i-1][1], d[i-1][2]);
        }
        int min = Math.min(d[n][0], Math.min(d[n][1], d[n][2]));
        
        System.out.println(max + " " + min);
    }
}
cs




<C++>


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
#include <iostream>
using namespace std;
 
int n;
int map[100001][3];
int maxd[2][3];
int mind[2][3];
 
int max(int a,int b) {
    if (a > b) {
        return a;
    }
    return b;
}
 
int min(int a, int b) {
    if (a < b) {
        return a;
    }
    return b;
}
 
int main() {
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> map[i][0] >> map[i][1] >> map[i][2];
    }
 
    mind[0][0] = maxd[0][0]  = map[1][0];
    mind[0][1] = maxd[0][1]  = map[1][1];
    mind[0][2] = maxd[0][2]  = map[1][2];
 
    for (int i = 2; i <= n; i++) {
        maxd[1][0] = map[i][0] + max(maxd[0][0], maxd[0][1]);
        maxd[1][1] = map[i][1] + max(maxd[0][0], max(maxd[0][1], maxd[0][2]));
        maxd[1][2] = map[i][2] + max(maxd[0][1], maxd[0][2]);
 
        maxd[0][0] = maxd[1][0];
        maxd[0][1] = maxd[1][1];
        maxd[0][2] = maxd[1][2];
 
        mind[1][0] = map[i][0] + min(mind[0][0], mind[0][1]);
        mind[1][1] = map[i][1] + min(mind[0][0], min(mind[0][1], mind[0][2]));
        mind[1][2] = map[i][2] + min(mind[0][1], mind[0][2]);
 
        mind[0][0] = mind[1][0];
        mind[0][1] = mind[1][1];
        mind[0][2] = mind[1][2];
    }
 
    int res1 = max(maxd[0][0], max(maxd[0][1], maxd[0][2]));
    int res2 = min(mind[0][0], min(mind[0][1], mind[0][2]));
    
    cout << res1 << " " << res2 << endl;
}
cs


저작자표시

'BOJ::문제풀이' 카테고리의 다른 글

2178 미로 탐색  (0) 2018.01.01
2156 포도주 시식  (0) 2018.01.01
1987 알파벳  (0) 2018.01.01
1965 상자넣기  (0) 2018.01.01
1934 최소공배수  (0) 2018.01.01

+ Recent posts

티스토리툴바