BOJ::1932 숫자삼각형

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


dp 문제이다.

d배열의 각 지점마다 올 수 있는 최대값을 저장해주면서 끝까지 가면 된다.


<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
46
47
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[501][501];
    static int map[][]=new int[501][501];
    
    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());
            int j =1;
            while(st.hasMoreTokens()){
                map[i][j]=Integer.parseInt(st.nextToken());
                j++;
            }
        }
        
        d[1][1]=map[1][1];
        for(int i = 2 ; i <= n ; i++){
            d[i][1]=map[i][1]+d[i-1][1];
            d[i][i]=map[i][i]+d[i-1][i-1];
            for(int j = 2 ; j < i ; j++){
                d[i][j]=map[i][j]+Math.max(d[i-1][j], d[i-1][j-1]);
            }
        }
        
        int max =0;
        for(int i = 1 ; i <= n ; i++){
            if(max <d[n][i]){
                max = d[n][i];
            }
        }
        System.out.println(max);
        
    }
}
 
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
#include <iostream>
using namespace std;
 
int n;
int d[501][501];
int map[501][501];
 
int max(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}
 
int main() {
    
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> map[i][j];
        }
    }
 
    d[1][1] = map[1][1];
 
    for (int i = 1; i <= n; i++) {
        d[i][1] = map[i][1] + d[i - 1][1];
        d[i][i] = map[i][i] + d[i - 1][i - 1];
        for (int j = 2; j < i; j++) {
            d[i][j] = map[i][j] + max(d[i - 1][j - 1], d[i - 1][j]);
        }
    }
 
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (max < d[n][i]) {
            max = d[n][i];
        }
    }
    cout << max << endl;
 
}
cs


저작자표시

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

1965 상자넣기  (0) 2018.01.01
1934 최소공배수  (0) 2018.01.01
1929 소수 구하기  (0) 2018.01.01
1920 수 찾기  (0) 2018.01.01
1890 점프  (0) 2017.12.31

+ Recent posts

티스토리툴바