Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
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
Archives
Today
Total
관리 메뉴

차근차근

[백준 1932] 정수 삼각형 본문

대학교/Algorithm

[백준 1932] 정수 삼각형

SWKo 2020. 2. 28. 12:02

0. 제목

  • 백준 1932 정수 삼각형
  • BOJ 1932 정수 삼각형
  • C++ 1932 정수 삼각형

1. 문제

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


2. 풀이

  • 합이 최대가 되는 경로에 있는 수의 합을 출력하는 것이 문제이다.
  • 2차원 배열 arr, dp를 할당하고 arr는 각 위치의 값이 담기고 dp는 그 위치로 갔을 때의 합이 담긴다.
  • 그런데 합이 최대가 되어야 하므로 전 단계에서 즉, 윗 줄에서 왼쪽과 오른쪽중 큰 것을 선택해야 한다.
  • 따라서 점화식은 다음과 같다.
  • dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j]
  • 그런데 좌표를 arr[1][1] 부터 시작하도록 설정하였으며 i-1 이 0이 나오는 dp[i][0]들은 0으로 초기화 시켜놓았기 때문에 계산상 문제가 없다.
  • 결론적으로 주어진 n번째 줄에서의 최대 합을 찾아야 하므로 최댓값을 구하는 알고리즘을 사용하면 된다.

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
#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[501][501];
int dp[501][501= {0};
 
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            cin >> arr[i][j];
        }
    }
    
    dp[1][1= arr[1][1];
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= i; j++){
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j];
        }
    }
    int max = 0;
    for(int i = 1; i <= n; i++){
        if(max < dp[n][i])
            max = dp[n][i];
    }
    
    cout << max << '\n';
    
    return 0;
}
 
 

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 2003] 수들의 합 2  (0) 2020.02.29
[백준 1789] 수들의 합  (0) 2020.02.29
[백준 1735] 분수 합  (0) 2020.02.27
[백준 7562] 나이트의 이동  (0) 2020.02.27
[백준 2252] 줄 세우기  (0) 2020.02.27
Comments