Backjoon Online Judge 

"1932번 : 숫자삼각형" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/1932


일단 문제에서 선택된 수의 최대값을 구하기 위해 DP를 이용하였습니다.


 - 먼저 삼각형을 저장할 2차원 배열과 각각에 대해 최대값을 저장할 2차원 배열을 선언했습니다. (입력값을 받아오자 마자 배열에 쓰고, 저장되는 최대값을 덮어쓰는 방식으로 구현한다면 1차원 배열 2개로도 구현이 가능하리라 생각합니다.)

 - 이후 삼각형의 특성 상 양쪽 끝 부분은 더해지는 경우의 수가 하나이므로 이전 최대값을 불러와 더했고, 중간 부분은 이전 최대값 중 큰 값을 이용하였습니다.


코드는 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
#include <iostream>
#include <algorithm>
#include <memory.h>
 
#define MAX 500
 
using namespace std;
 
int main() {
    int maxTriangle[MAX][MAX];    //n번째까지의 maxTriangle값
    int triangle[MAX][MAX];        //주어진 삼각형의 값
    int n;                        //삼각형의 크기
    int result = 0;
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> triangle[i][j];
        }
    }
 
    maxTriangle[0][0] = triangle[0][0];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                maxTriangle[i][j] = maxTriangle[i - 1][j];
            }
            else if (j == i) {
                maxTriangle[i][j] = maxTriangle[i - 1][j - 1];
            }
            else {
                maxTriangle[i][j] = max(maxTriangle[i - 1][j - 1], maxTriangle[i - 1][j]);
            }
            maxTriangle[i][j] += triangle[i][j];
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (maxTriangle[n - 1][i] > result) {
            result = maxTriangle[n - 1][i];
        }
    }
    cout << result << endl;
    cin >> n;
    return 0;
}

cs



저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

1463번 : 1로 만들기  (0) 2018.05.10
2579번 : 계단 오르기  (0) 2018.05.05
1149번 : RGB거리  (0) 2018.04.01
1003번 : 피보나치 함수  (0) 2018.04.01
2749번 : 피보나치 수 3  (0) 2018.04.01

티스토리툴바