[Baekjoon Online Judge] 백준 1932번 정수 삼각형(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1932번 정수 삼각형

(C++, Python)

(글쓴날 : 2020.04.12)

 

---

* Baekjoon Online Judge, 백준 1932번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1932번 정수 삼각형

---

1) 문제

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

1932번: 정수 삼각형

---

2) 풀이 과정

길이가 N인 2차원 배열에 정수들이 삼각형 모양으로 주어질 때, 맨 위층부터 아래층까지 내려가면서 선택된 수의 합이 최대인 경우를 구하는 문제입니다.

단, 아래층에 있는 수는 선택된 수 위층의 대각선 왼쪽 혹은 오른쪽에 있는 수 중에서만 선택할 수 있습니다.

 

저의 경우, 동적 계획법을 적용하여 문제에 접근하였으며, C++과 Python을 사용했습니다.

보통, 동적 계획법을 적용할 때 memoization을 위해 이전 결과들을 저장하는 배열을 따로 선언하지만,

이 문제는 그럴 필요 없이 층을 내려갈 때마다 위층에서 선택 가능한 수 중 큰 값을 더해 덮어씌우면서 내려가다 보면 마지막 층에 저장된 값들이 해당 인덱스로 올 수 있는 최대 합이 됩니다.

따라서, 마지막 층에 있는 값들 중 최댓값을 출력하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int triangle[501][501];
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            cin >> triangle[i][j];
        }
    }
 
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            if (j == 0)
                triangle[i][j] += triangle[i - 1][j];
            else if (j == i)
                triangle[i][j] += triangle[i - 1][j - 1];
            else
            {
                if (triangle[i - 1][j] > triangle[i - 1][j - 1])
                    triangle[i][j] += triangle[i - 1][j];
                else
                    triangle[i][j] += triangle[i - 1][j - 1];
            }
        }
    }
 
    cout << *max_element(triangle[n - 1], triangle[n - 1] + n);
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]
 
for i in range(1, n):
    for j in range(i + 1):
        if j == 0:
            triangle[i][j] += triangle[i - 1][j]
        elif j == i:
            triangle[i][j] += triangle[i - 1][j - 1]
        else:
            if triangle[i - 1][j - 1] > triangle[i - 1][j]:
                triangle[i][j] += triangle[i - 1][j - 1]
            else:
                triangle[i][j] += triangle[i - 1][j]
 
print(max(triangle[n - 1]))

---